[BaekJoon] 1726 로봇 :: monton

문제

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

풀이

가중치 없이 최단 거리를 구하는 문제이므로 bfs 사용

일단 현재 위치에서 방향에 따라 visit 처리를 해주어야 하므로 visit[MAX][MAX][5]로 해주어야 한다

이 문제를 두가지 이유때문에 틀렸는데

첫번째는 최단 거리를 구하는 문제라 생각하고 습관적으로 상하좌우 방향을 모두 살폈다는 점이다

이 문제는 이동거리에 따른 카운트가 아니라 명령 횟수에 따른 카운트 이다

이 명령에는 turn도 명령 카운트에 들어가므로 상하좌우 방향으로 함부로 카운트 하면 안된다

현재 방향에서 1,2,3 go 명령에 카운트 해주고 좌,우로 90도 turn 해준것을 카운트 한다

두번째는 주어진 방향이 내가 코드로 짜기 편하게 바꾸어야 하는데 설정을 잘못해서 틀렸다

동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어지므로 초기에 바꾸어 놓아야 사용하기 편하다

코드

#include <iostream>
#include <queue>
 
using namespace std;
 
int N, M,ans,flag;
int arr[101][101];
int visit[101][101][5];
int dir[4][4] = { {-1,0},{0,1},{1,0},{0,-1} };
int q, w, e;
 
queue<int> qx, qy, qd;
 
int changdir(int e) {
    if (e == 1) return 1;
    if (e == 2) return 3;
    if (e == 3) return 2;
    if (e == 4) return 0;
}
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
    
    cin >> q >> w >> e;
    e = changdir(e);
    qx.push(q-1), qy.push(w-1), qd.push(e);
    visit[q - 1][w - 1][e] = 1;
    cin >> q >> w >> e;
    q -= 1, w -= 1;
    e=changdir(e);
 
    while (!qx.empty()) {
        int qcnt = qx.size();
        while (qcnt--) {
            int x = qx.front();
            int y = qy.front();
            int d = qd.front();
            qx.pop(), qy.pop(), qd.pop();
 
            if (x == q&&y == w&&e == d) {
                cout << ans;
                return 0;
            }
 
            for (int i = 1; i <= 3; i++) {
                int nx = x + i*dir[d][0];
                int ny = y + i*dir[d][1];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) break;
                if (arr[nx][ny]) break;
                if (visit[nx][ny][d]) continue;
 
                qx.push(nx), qy.push(ny), qd.push(d);
                visit[nx][ny][d] = 1;
                
            }
 
            int rd = d;
            int ld = d;
            rd = rd + 1 == 4 ? 0 : rd + 1;
            ld = ld - 1 == -1 ? 3 : ld - 1;
            if(!visit[x][y][rd]) qx.push(x), qy.push(y), qd.push(rd), visit[x][y][rd]=1;
            if (!visit[x][y][ld]) qx.push(x), qy.push(y), qd.push(ld),visit[x][y][ld]=1;
    
        }
        ans++;
    }
}