백준 20420 자바 - 화살표 미로 (Normal) (BOJ 20420 JAVA)

문제 : boj20420

 

 

  매운맛의 BFS 문제였다. BFS에 대해서는 여기에 작성해놨다.

위의 '여기' 글을 읽어 곰을 구해주세요(?)

해당 글의 내용만 있으면 풀 수 있는 문제이다. 이 문제를 풀 수 있는 BFS 적용 아이디어를 작성해보겠다.

 

A. BFS 진행 시 인접한 곳은 원래 주어진 방향, 좌측으로 회전해서 갈 수 있는 만큼의 방향(예를들어 남은 L이 2라면 좌측으로 2번까지 돌 수 있다.), 우측으로 회전해서 갈 수 있는 만큼의 방향 이다.

 

B. 좌측으로 4번 혹은 우측으로 4번을 돌면 원래 방향이 되므로 무조건 손해이다. 따라서 좌측으로 3번, 우측으로 3번까지만 확인해야 한다. 이 때, 예를들어 좌측으로 3번이 우측으로 1번과 동일하다고 해서 2번까지만 확인하면 안된다. 남은 횟수가 한쪽이 더 많을 수도 있다.

 

C. 방문체크는 모든 경우를 포함할 수 있어야 한다. 이 문제에서 모든 경우에 해당하는 방문체크는 r, c의 위치에 L과 R이 몇 번 남은 채로 도착했는지 체크하는 것이다. 따라서 내 경우 v[r][c][k+1][k+1]의 4차원 방문배열을 사용했다. 예를들어 v[2][1][1][2]가 true라면 r=2, c=1인 지점에 L이 1 남고, R이 2 남은채로 도착한 적이 있다는 의미이다.

 

D. 좌측으로 회전, 우측으로 회전을 편하게 하려면 순서대로 U,R,D,L을 0부터 3까지로 지정하면 된다. 이 경우 우측으로 돈다면 현재 방향+1을 해주면 되고, 좌측으로 돈다면 -1을 해주면 된다. 그리고 방향이 4 이상이 된다면 4를 빼주거나 4로 나눈 나머지로 변경하고, 방향이 음수가 된다면 4를 더해주면 맞는 방향이 된다. 예를들어 현재 방향이 D(2)이고 우측으로 3번 돈다면 2+3 = 5이고, 5-4 = 1 이므로 'R'이 된다.

 

정리하자면 현재 위치에서 원래 주어진 방향으로도 가보고, 남은 L과 R만큼 회전하면서도 가보면서 BFS를 진행하면 된다. 이 때 방문체크는 현재의 지점(r, c)과 남은 L, R의 개수로 하면 된다. 최종적으로 우측 아래에 도착한다면 바로 "Yes"를 출력하고 종료하면 되고, 큐가 빌 때 까지 도달하지 못했다면 "No"가 된다.

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    class Room {
        int r, c, left, right;
        public Room(int r, int c, int left, int right) {
            this.r = r;
            this.c = c;
            this.left = left;
            this.right = right;
        }
    }
    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {0, 1, 0, -1};
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] arr = new int[r][c];
        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                int d = 0;
                switch (row.charAt(j)) {
                    case 'U' : d=0; break;
                    case 'R' : d=1; break;
                    case 'D' : d=2; break;
                    case 'L' : d=3; break;
                }
                arr[i][j] = d;
            }
        }

        Queue<Room> q = new ArrayDeque<>();
        boolean[][][][] v = new boolean[r][c][k+1][k+1];
        q.add(new Room(0, 0, k, k));
        v[0][0][k][k] = true;
        while (!q.isEmpty()) {
            Room cur = q.poll();
            int s = Math.max(-cur.left, -3)-1;
            int e = Math.min(cur.right, 3);
            while (++s<=e) {
                int dir = arr[cur.r][cur.c] + s;
                if (dir < 0) dir+=4;
                if (dir >= 4) dir%=4;

                int nr = cur.r + dr[dir];
                int nc = cur.c + dc[dir];
                int nLeft = cur.left+(s<0?s:0);
                int nRight = cur.right-(s>0?s:0);

                if (nr<0||nr>=r||nc<0||nc>=c||v[nr][nc][nLeft][nRight]) continue;
                if (nr==r-1 && nc==c-1) {
                    System.out.println("Yes");
                    return;
                }

                v[nr][nc][nLeft][nRight] = true;
                q.add(new Room(nr, nc, nLeft, nRight));
            }
        }
        System.out.println("No");
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}