[Algorithm] Baekjoon 1600번 : 말이 되고픈 원숭이

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

1600번: 말이 되고픈 원숭이

int width;
int height;
int hmMax;
 
bool visited[201][201][31];
bool gameMap[201][201];
 
vector<vector<int>> dir = { {-1,0}, {1,0}, {0,-1}, {0,1} };
vector<vector<int>> hmDir = { {2,1},{2,-1}, {-2,1}, {-2,-1}, {1,2}, {1,-2}, {-1,2}, {-1,-2} };
 
struct Node
{
    int y;
    int x; 
    int count;
    int hmCount;
 
    Node() {};
    Node(int _y, int _x, int _count, int _hmCount) : y(_y), x(_x), count(_count), hmCount(_hmCount) {};
};
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int answer = -1;
    cin >> hmMax >> width >> height;
    
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            cin >> gameMap[i][j];
        }
    }
 
    queue<Node> q;
    q.push(Node(0, 0, 0, 0));
 
    while (!q.empty())
    {
        Node curNode = q.front();
        q.pop();
 
        int curY = curNode.y;
        int curX = curNode.x;
        int curCount = curNode.count;
        int curHMCount = curNode.hmCount;
 
        if (curY == height - 1 && curX == width - 1)
        {
            answer = curCount;
            break;
        }
 
        for (int i = 0; i < dir.size(); i++) // 원숭이이동 
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= height) continue;
            if (nextX < 0 || nextX >= width) continue;
            if (gameMap[nextY][nextX]) continue;
            if (visited[nextY][nextX][curHMCount]) continue;
 
            visited[nextY][nextX][curHMCount] = true;
            q.push(Node(nextY, nextX, curCount + 1, curHMCount));
        }
 
        if (curHMCount < hmMax)
        {
            for (int i = 0; i < hmDir.size(); i++) // 말 이동.
            {
                int nextY = curY + hmDir[i][0];
                int nextX = curX + hmDir[i][1];
 
                if (nextY < 0 || nextY >= height) continue;
                if (nextX < 0 || nextX >= width) continue;
                if (gameMap[nextY][nextX]) continue;
                if (visited[nextY][nextX][curHMCount + 1]) continue;
 
                visited[nextY][nextX][curHMCount + 1] = true;
                q.push(Node(nextY, nextX, curCount + 1, curHMCount + 1));
                
            }
        }
 
    }
 
    cout << answer;
    
    return 0;
}

 

평상시 풀던 BFS문제에서 좀 더 응용해야하는 문제.

이동하려는 칸에 대해서 말의 이동도 체크를 해줘야한다.

그렇기 때문에 visited를 차원을 하나 더늘려서 3차원으로 관리한다.

해당 칸에 이미 동일한 횟수의 말이동이 적용 됐었던 상태라면, 중복된 노드가 큐에 들어갈 수 있기 때문이다.