BOJ 17836 [공주님을 구해라!]

BOJ 공주님을 구해라! : www.acmicpc.net/problem/17836

17836번: 공주님을 구해라!

간단한 BFS 문제이다.

 

키포인트는 방문배열(visit)를 3차원으로 설정했다.

 

visited[3][3][0] => 그람 없이 (3, 3)을 방문한 경우

visited[3][3][1] => 그람을 가지고 (3, 3)을 방문한 경우

 

그람을 획득하면, 해당 node가 그람을 가지도록 체크해준다.

#include <iostream>
#include <queue>
using namespace std;
 
int N, M, T;
bool visited[100][100][2];
int map[100][100];
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };
 
class Node
{
public:
    int x, y, time;
    int gram;
    Node(int x, int y, int time, int gram)
    {
        this->x = x;
        this->y = y;
        this->time = time;
        this->gram = gram;
    }
};
queue<Node> q;
 
bool IsBoundary(int x, int y)
{
    return x >= 0 && x < N && y >= 0 && y < M;
}
 
int Bfs()
{
    q.push(Node(0, 0, 0, false));
    visited[0][0][0] = true;
 
    while (!q.empty())
    {
        Node node = q.front();
        q.pop();
 
        if (node.time > T)
        {
            return 0;
        }
 
        if (node.x == N - 1 && node.y == M - 1)
        {
            return node.time;
        }
 
        for (int i = 0; i < 4; i++)
        {
            int nextX = node.x + dx[i];
            int nextY = node.y + dy[i];
 
            if (IsBoundary(nextX, nextY))
            {
                switch (map[nextX][nextY])
                {
                case 0:
                    if (!visited[nextX][nextY][node.gram])
                    {
                        visited[nextX][nextY][node.gram] = true;
                        q.push(Node(nextX, nextY, node.time + 1, node.gram));
                    }
                case 1:
                    if (node.gram == 1)
                    {
                        if (!visited[nextX][nextY][1])
                        {
                            visited[nextX][nextY][1] = true;
                            q.push(Node(nextX, nextY, node.time + 1, node.gram));
                        }
                    }
                    break;
                case 2:
                    if (!visited[nextX][nextY][1])
                    {
                        visited[nextX][nextY][1] = true;
                        q.push(Node(nextX, nextY, node.time + 1, 1));
                    }
                    break;
                }
            }
        }
    }
 
    return 0;
}
 
int Solution_17836()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> N >> M >> T;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
        }
    }
 
    int result = Bfs();
 
    if (result == 0)
    {
        cout << "Fail";
    }
    else 
    {
        cout << result;
    }
    return 0;
}