www.acmicpc.net/problem/20419

 

20419번: 화살표 미로 (Easy)

첫번째 줄에는 미로의 행 R, 열 C, 준서가 가진 주문서 세트의 개수 K가 주어진다. 두번째 줄부터 R줄에 걸쳐 화살표 미로의 지도가 입력된다. 각 줄마다 "UDLR"로만 이루어진 길이 C의 문자열이 입

www.acmicpc.net

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

 

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

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

 

아무튼..

 

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

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

 

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

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
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();
    }
}
cs

'algorithm > bfs' 카테고리의 다른 글

boj 1012 유기농 배추  (0) 2021.02.03
boj 16956 늑대와 양  (0) 2021.02.03
boj 2638 치즈  (0) 2021.01.22
boj 17142 연구소 3  (0) 2021.01.22
boj 2636 치즈  (0) 2021.01.22

+ Recent posts

티스토리툴바