[백준] 25960 : 폰의 각성

https://www.acmicpc.net/problem/25960

문제 분석

 시작 지점인 폰의 위치에서 다른 기물(비숍, 룩, 퀀, 나이트)등을 경유하여 킹의 위치로 최소 비용으로 이동하는 문제이다. 이때, 기물과 기물 간만 이동가능하며(기물이 없는 빈칸으로 이동불가), 이동 방식은 시작 지점의 기물의 이동방식을 따르고 한 번 방문한 기물로는 재방문이 불가능하다.
 더 생각할 것도 없이 폰을 시작, 킹을 도착 지점, 각 기물을 노드로 가지는 다익스트라 문제이다. 다익스트라는 최소 거리를 찾는 과정에서 이미 방문한 노드를 다시 방문하지 않으므로 각 기물 별 이동가능한 이웃 기물 들만 잘 설정하여 풀면된다.

문제 해결 전략

 각 기물 별로 이동방식이 다른 만큼 기물의 종류(_type), 위치(_x, _y), 이웃( _neighbours )을 멤버 변수로 가지고 특정 위치의 노드의 유효성을 체크하고 이웃에 해당 노드를 추가하는 멤버 메소드(isvalid)를 가지는 기본 클래스(Piece)를 설정하고 해당 노드를 상속받아 이웃 노드를 설정하는 멤버 메소드(SetNeighbours)를 오버라이드 하는 체스 기물 클래스 들을 구현하였다.
 보드 사이즈를 입력받고 입력 정보에 따라 기물의 인스턴스를 생성하는 메소드는 편의상 static 변수와 메소드로 piece 클래스내에 구현하였다. 또한, 실제 다익스트라 알고리즘을 수행하는 구현부 역시 piece 클래스내에 구현하였다.
 마지막으로 필자가 헤맸던 부분인데, 이웃노드 설정 시 폰의 경우는 단순 시작위치이므로 비숍, 룩, 퀀 등의 진로를 방해하지 않는다는 점을 주의하여 구현하여야한다.

코드

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>

using namespace std;
class Null;
class King;
class Pawn;
class Bishop;
class Rook;
class Knight;
class Queen;

class Piece{
public:
    Piece(int x, int y) : _x(x), _y(y) {}
    virtual void SetNeighbours() {};
    const vector<pair<Piece*,int>>& GetNeighbours() const{
        return _neighbours;
    }
    const char& GetType() const{return _type;};
    bool isValid(int x, int y){
        if(!(0<=x && x<boardSize && 0<=y && y<boardSize)) return false;
        if(board[x][y]->GetType()!='0' && board[x][y]->GetType()!='P'){
            _neighbours.push_back({board[x][y],max(abs(x-_x),abs(y-_y))});
            return false;
        }
        return true;
    }
    static void SetBoard();
    static void SetBoardNeighbours();
    static void Print();
    static int  Solution();
protected:
    vector<pair<Piece*,int>> _neighbours;
    static int boardSize;
    static vector<vector<Piece*>> board;
    char _type='0';
    int _x, _y;

    bool isvisited = false;
    int dist = -1;
private:
    static Pawn* pawn;
    static King* king;
};

class Null : public Piece{
public:
    Null(int x, int y) : Piece(x,y){_type='0';};
};

class King : public Piece{
public:
    King(int x, int y) : Piece(x,y){_type='K';};
};


class Pawn : public Piece{
public:
    Pawn(int x, int y) : Piece(x,y){_type='P';};
    void SetNeighbours() override{
        int dx[]={-1,-1,-1,+1,+1,+1,+0,+0};
        int dy[]={-1,+1,+0,-1,+1,+0,-1,+1};
        for (size_t i = 0; i < 8; i++)
        {
            int nx(_x+dx[i]),ny(_y+dy[i]);
            isValid(nx,ny);
        }
    };
};

class Rook : virtual public Piece{
public:
    Rook(int x, int y) : Piece(x,y){_type='R';};
    void SetNeighbours() override{
        for (size_t i = 1; i < boardSize; i++)
        {
            int nx(_x),ny(_y+i);
            if (!isValid(nx,ny)) break;
        }
        for (size_t i = 1; i < boardSize; i++)
        {
            int nx(_x),ny(_y-i);
            if (!isValid(nx,ny)) break;
        }
        for (size_t i = 1; i < boardSize; i++)
        {
            int nx(_x+i),ny(_y);
            if (!isValid(nx,ny)) break;
        }
        for (size_t i = 1; i < boardSize; i++)
        {
            int nx(_x-i),ny(_y);
            if (!isValid(nx,ny)) break;
        }
    };
};

class Bishop : virtual public Piece{
public:
    Bishop(int x, int y) : Piece(x,y){_type='B';};
    void SetNeighbours() override{
        for (size_t i = 1; i < boardSize; i++)
        {
            int nx(_x+i),ny(_y+i);
            if (!isValid(nx,ny)) break;
        }
        for (size_t i = 1; i < boardSize; i++)
        {
            int nx(_x-i),ny(_y-i);
            if (!isValid(nx,ny)) break;
        }
        for (size_t i = 1; i < boardSize; i++)
        {
            int nx(_x+i),ny(_y-i);
            if (!isValid(nx,ny)) break;
        }
        for (size_t i = 1; i < boardSize; i++)
        {
            int nx(_x-i),ny(_y+i);
            if (!isValid(nx,ny)) break;
        }
    };
};

class Queen : public Bishop, public Rook{
public:
    Queen(int x, int y) : Piece(x,y), Bishop(x,y), Rook(x,y) {_type='Q';};
    void SetNeighbours() override{
        Bishop::SetNeighbours();
        Rook::SetNeighbours();
    };
};

class Knight : public Piece{
public:
    Knight(int x, int y) : Piece(x,y){_type='K';};
    void SetNeighbours() override{
        int dx[]={-2,-2,-1,-1,+1,+1,+2,+2};
        int dy[]={-1,+1,-2,+2,-2,+2,-1,+1};
        for (size_t i = 0; i < 8; i++)
        {
            int nx(_x+dx[i]),ny(_y+dy[i]);
            isValid(nx,ny);
        }
    };
};

void Piece::SetBoard(){
cin >> boardSize;
board=vector<vector<Piece*>>(boardSize,vector<Piece*>());
for(int i=0; i<boardSize; i++)
    for(int j=0; j<boardSize; j++){
        char piece_type;
        cin >> piece_type;
        Piece* piece;
        switch (piece_type)
        {
        case '0':
            piece=new Null(i,j);
            break;
        case 'K':
            piece=new King(i,j);
            king = dynamic_cast<King*>(piece);
            break;
        case 'P':
            piece=new Pawn(i,j);
            pawn = dynamic_cast<Pawn*>(piece);
            break;
        case 'B':
            piece=new Bishop(i,j);
            break;
        case 'R':
            piece=new Rook(i,j);
            break;
        case 'N':
            piece=new Knight(i,j);
            break;
        case 'Q':
            piece=new Queen(i,j);
            break;
        
        default:
            break;
        }
        board[i].push_back(piece);
    }
}

void Piece::SetBoardNeighbours()
{
    for(int i=0; i<boardSize; i++)
        for(int j=0; j<boardSize; j++)
            board[i][j]->SetNeighbours();
}

int Piece::Solution(){
    priority_queue<pair<int,Piece*>,vector<pair<int,Piece*>>,greater<pair<int,Piece*>>> heapq;
    heapq.push({0,pawn});
    pawn->dist=0;
    while(!heapq.empty()){
        Piece* curPiece =heapq.top().second;
        int cost =heapq.top().first;
        heapq.pop();
        if ((curPiece->isvisited)) continue;
        curPiece->isvisited=true;
        curPiece->dist=cost;
        for(const auto& piece : curPiece->GetNeighbours()){
            if (!piece.first->isvisited){
                heapq.push({cost+piece.second,piece.first});
            }
        }
    }

    return king->dist;
}

int Piece::boardSize;
vector<vector<Piece*>> Piece::board;
King* Piece::king=nullptr;
Pawn* Piece::pawn=nullptr;

int main()
{
    Piece::SetBoard();
    Piece::SetBoardNeighbours();
    cout << Piece::Solution() << endl;
}