[Algorithm] Baekjoon 1726번 : 로봇

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

1726번: 로봇

struct Node
{
    int y;
    int x;
    int dir;
    int count;
};
 
int m, n;
int arr[102][102];
bool visited[102][102][4] = { false };
int dirs[4][2] = { {0,1}, {0,-1}, {1,0}, {-1,0} };
int start[3];
int dest[3];
 
bool checkRange(int y, int x)
{
    if (y < 0 || y >= m || x < 0 || x >= n) return false;
    return true;
}
 
int getDirLR(int dir, bool isLeft)
{
    if (isLeft)
    {
        switch (dir)
        {
        case 0: return 3;
        case 1: return 2;
        case 2: return 0;
        case 3: return 1;
        }
    }
    else
    {
        switch (dir)
        {
        case 0: return 2;
        case 1: return 3;
        case 2: return 1;
        case 3: return 0;
        }
    }
}
 
void BFS()
{
    queue<Node> q;
    q.push({ start[0],start[1],start[2],0 });
    visited[start[0]][start[1]][start[2]] = true;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curDir = q.front().dir;
        int curCount = q.front().count;
        q.pop();
 
        if (curY == dest[0] && curX == dest[1] && curDir == dest[2])
        {
            cout << curCount;
            return;
        }
 
        for (int i = 1; i <= 3; ++i)
        {
            int nextY = curY + dirs[curDir][0] * i;
            int nextX = curX + dirs[curDir][1] * i;
 
            if (!checkRange(nextY, nextX)) break;
            if (arr[nextY][nextX] == 1) break;
            if (visited[nextY][nextX][curDir]) continue;
 
            visited[nextY][nextX][curDir] = true;
            q.push({ nextY,nextX,curDir,curCount+1});
        }
        
        // 왼쪽 오른쪽 검사.
        int curLeft = getDirLR(curDir, true);
        int curRight = getDirLR(curDir, false);
 
        if (visited[curY][curX][curLeft] == false)
        {
            visited[curY][curX][curLeft] = true;
            q.push({ curY,curX,curLeft,curCount+1 });
        }
 
        if (visited[curY][curX][curRight] == false)
        {
            visited[curY][curX][curRight] = true;
            q.push({ curY,curX,curRight,curCount+1});
        }
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> m >> n;
 
    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    cin >> start[0] >> start[1] >> start[2];
    cin >> dest[0] >> dest[1] >> dest[2];
    
    for (int i = 0; i < 3; ++i) start[i] -= 1;
    for (int i = 0; i < 3; ++i) dest[i] -= 1;
 
    BFS();
}

회전까지 고려해야하는 BFS문제이다.

현재 방향으로 1~3칸에 대한 부분을 큐에 넣어준다.

그리고 '현재위치'에서 회전한 상태를 큐에 넣어준다.

여기서 주의할 점은.. 회전한다음 이동한걸 큐에넣는게아니라 회전만 시킨걸 큐에 넣는거다.

그리고 1~3칸 이동할 때, 이동지점이 벽이거나 범위를 벗어나면 continue가 아니라 break를 해버리는게 좀 더 시간효율이 좋다.

어차피 +1칸 검사할 때 벽이면 막혀있기 때문에 당연히 +2,+3칸 이동은 불가능하고 범위를 벗어나는 것 또한 마찬가지이기 때문이다.

다만 visited[nextY][nextx][curDir]이 false라면 break가 아니라 continue를 계속 해주는데, 왜냐하면 해당칸에 먼저 갔다고 무조건 해당노드가 뻗어나갈 노드들이 최선의 노드가 아니기 때문이다.

이게 성립하는 이유는 +1칸이동이 아닌 +2,+3칸 이동이 같은 count로 취급되기 때문이다.

 

예를 들어 1,1에 북쪽을 바라보는 노드가 먼저 들어왔다고 가정한다. 그리고 두번째 루트의 노드는 0,1인 상태에서 동쪽을 바라보고 있다. 이상태에서 갈수있는 방향은 무조건 동쪽으로 뻗어나가야 한다.

 

1,1에있는게 먼저들어왔기 때문에 로직을 수행한다. 북쪽으로 +1~+3이동은 막혀있기때문에 불가능하니까, 동쪽으로 회전하고 visited에 체크를한다.

그러면 visited[1][1][0] = true가 된다.

그다음에는 0,1에 있는 노드가 로직을 수행할 것이다. 이 노드는 이미 동쪽을 바라보고 있었기 때문에 먼저 +1칸에 대해 검사한다. 즉, visited[1][1][0]이 false인지 true인지 검사할 것이다.

근데 이전에 검사했던, 원래 1,1에 있던 노드가 이미 true로 체크해버렸었기 때문에 0,1 노드의 로직으로는 해당 if문에서 걸려버린다. 

여기서 break를 해버린다? 절대 그러면 안된다. 왜냐하면 +2, +3을 같은 값(count)로 이동이 가능하기 때문이다.

1,1이 아니라 1,2 혹은 1,3에 먼저 가버릴 수 있기 때문이다. 그렇기 때문에 break가 아니라 반드시 continue로 해야된다.