boj 20419 화살표 미로 (Easy)

www.acmicpc.net/problem/20419

20419번: 화살표 미로 (Easy)

문제를 잘못 이해하는 바람에 4번이나 WA를 받고 깨달았습니다...

 

이 문제는 (1, 1)에서 (R, C)로 이동하면 탈출하는 문제입니다.

저는 (R, C)에서 오른쪽으로 가느니 밑으로 가느니 이런 삽질을 하였습니다 ㅠㅠ

 

아무튼..

 

문제는 bfs로 해결하였습니다.

K가 0아니면 1이었기 때문에 queue에 {x좌표, y좌표, 주문서 사용}를 저장하였고,

 

해당 칸에 명시되어 있는 방향으로 이동한 좌표, 주문서를 사용하며 이동한 좌표 모두 queue에 담으며 탐색하였습니다.

 

 

package BOJ.bfs;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Boj20419 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][];
    static int direct[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
    static boolean visit[][][];
    static int N, M, K;
 
    static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { 0, 0, 0 });
        visit[0][0][0] = true;
        while (!q.isEmpty()) {
            int x = q.peek()[0];
            int y = q.peek()[1];
            int k = q.peek()[2];
            q.remove();
 
            if (x == N - 1 && y == M - 1) {
                System.out.println("Yes");
                return;
            }
 
            int d = list[x][y];
            int nx = x + direct[d][0];
            int ny = y + direct[d][1];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                if (!visit[nx][ny][k]) {
                    q.add(new int[] { nx, ny, k });
                    visit[nx][ny][k] = true;
                }
            }
 
            if (K > 0) {
                if ((1 & k) == 0) { // Left
                    int nk = k | 1;
                    int nd = d - 1;
                    if (nd == -1)
                        nd = 3;
 
                    nx = x + direct[nd][0];
                    ny = y + direct[nd][1];
                    if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                        if (!visit[nx][ny][nk]) {
                            q.add(new int[] { nx, ny, nk });
                            visit[nx][ny][nk] = true;
                        }
                    }
                }
 
                if ((2 & k) == 0) { // Right
                    int nk = k | 2;
                    int nd = d + 1;
                    if (nd == 4)
                        nd = 0;
 
                    nx = x + direct[nd][0];
                    ny = y + direct[nd][1];
                    if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                        if (!visit[nx][ny][nk]) {
                            q.add(new int[] { nx, ny, nk });
                            visit[nx][ny][nk] = true;
                        }
                    }
                }
            }
 
        }
 
        System.out.println("No");
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new int[N][M];
        visit = new boolean[N][M][4];
        K = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            for (int j = 0; j < M; j++) {
                char ch = str.charAt(j);
                if (ch == 'U')
                    list[i][j] = 0;
                else if (ch == 'R')
                    list[i][j] = 1;
                else if (ch == 'D')
                    list[i][j] = 2;
                else
                    list[i][j] = 3;
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        bfs();
    }
}