[백준] 1726번 : 로봇

1726번: 로봇

---

[우선순위 큐 + BFS]

우선순위 큐를 사용한 이유에 대해서는 이따 반례와 함께 언급하고, 큐에 들어가야 하는 원소는 4가지 이다. 위치의 좌표(y, x), direction, 명령을 실행한 횟수(cnt)이다. 방향은 4가지 (동:1, 서:2, 남:3, 북:4)이고, 각 칸으로 최대 3칸 까지 갈 수 있으므로,

int[][] X =

{{1, 2, 3},

{-1, -2, -3},

{0, 0, 0},

{0, 0, 0}}

 

int[][] Y =

{{0, 0, 0},

{0, 0, 0},

{1, 2, 3},

{-1, -2, -3}};

의 2차원 배열을 초기화한다. 이는 각 동, 서, 남, 북을 가르키고, 1, 2, 3칸을 갈 수 있는 배열이다. 단, 현재 좌표에서 1칸이든 2칸이든 앞에 '1'(벽)이 있다면 그 이후의 칸에 대해서는 갈 수 없음을 유의한다.

 

그리고 회전하는 것에 대해 명령 실행 횟수를 추가하는 것은

동 -> 서 혹은 서 -> 동 및 북 -> 남 혹은 남 -> 북 일 때를 제외하고는, 1칸 씩 추가하게 된다.

2칸씩 추가하게 되는 것. 즉 동->서, 남->북을 숫자로 정의하였다.

 

동:1 서:2 이므로, 서로 다른 임의의 방향 2개를 더해 3이 된다면, 각각 동, 서 임이 분명하므로 명령 실행 횟수를 2 추가한다.

남:3 북:4 이므로, 서로 다른 임의의 방향 2개를 더해 7이 된다면, 각각 북, 남 임이 분명하므로 명령 실행 횟수를 2 추가한다.

 

우선순위 큐를 쓴 이유:

5 6
1 1 1 1 1 1
1 0 0 0 0 1
1 0 1 1 0 1
1 0 0 0 0 1
1 1 1 1 1 1
2 2 3
4 5 1

답:3 오답:4

Red에서 Blue로 가야하는데, 시작 방향이 남쪽을 향해있고, 도착 방향은 동쪽을 향해있다. 따라서 3번만에 갈 수 있는데, 일반 큐를 쓰면 들어가는 순서에 따라 원소가 나오게 되어, 항상 최적해를 찾진 못한다. 따라서 우선순위 큐를 사용함으로써 더 적은 비용으로 도착 정점에 도달하는 것을 추구하도록 한다.

# Code </>

public class Main {

    static class Point implements Comparable<Point>{
        int y, x, dir, cnt;

        public Point(int yy, int xx, int dir, int cnt){
            y=yy; x=xx;
            this.dir=dir;
            this.cnt=cnt;
        }
        @Override
        public int compareTo(Point o) {
            return cnt - o.cnt;
        }        
    }

    static int n, m;
    static int[][] map = new int[101][101], dp = new int[101][101];
    static boolean[][] visit = new boolean[101][101];
    static int[][] X = {{1, 2, 3}, {-1, -2, -3}, {0, 0, 0}, {0, 0, 0}}, Y = {{0, 0, 0}, {0, 0, 0}, {1, 2, 3}, {-1, -2, -3}};

    static int BFS(Point start, Point end){

        Queue<Point> Q = new PriorityQueue<>();

        visit[start.y][start.x] = true;
        dp[start.y][start.x] = 0;
        Q.add(new Point(start.y, start.x, start.dir, 0));

        while(!Q.isEmpty()){
            Point p = Q.poll();

            if(p.y == end.y && p.x == end.x) {

                if(p.dir == end.dir);
                else if(p.dir + end.dir == 3 || p.dir + end.dir == 7) p.cnt += 2;
                else p.cnt +=1;

                return p.cnt;
            }

            int y = p.y;
            int x = p.x;
            int dir = p.dir;
            int cnt = p.cnt;

            for(int a=1; a<=4; a++) {
                for (int b = 0; b < 3; b++) {
                    int ny = y + Y[a - 1][b];
                    int nx = x + X[a - 1][b];
                    int nCnt = cnt + 1;

                    if (ny < 1 || nx < 1 || ny > n || nx > m || visit[ny][nx]) continue;
                    if(map[ny][nx] == 1) break;

                    if (a == dir) nCnt += 0;
                    else if ((a + dir) == 3 || (a + dir) == 7) nCnt += 2;
                    else nCnt += 1;

                    visit[ny][nx] = true;
                    dp[ny][nx] = nCnt;
                    Q.add(new Point(ny, nx, a, nCnt));
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=m; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }

        Point[] points = new Point[2];
        for(int i=0; i<2; i++){
            st = new StringTokenizer(br.readLine());
            int Y = Integer.parseInt(st.nextToken());
            int X = Integer.parseInt(st.nextToken());
            int Dir = Integer.parseInt(st.nextToken());
            points[i] = new Point(Y, X, Dir, 0);
        }

        System.out.println(BFS(points[0], points[1]));
    }
}