https://www.acmicpc.net/problem/2931
문제 이해
- 공백(’.’)을 파이프 블록으로 바꿔 M에서 Z로 가는 파이프 경로를 이어야 합니다.
- 항상 답이 존재하고, 가스의 흐름이 유일한 경우만 입력으로 주어지므로 공백 주변의 파이프롤 확인하여 이어주기만 하면 됩니다.
접근 방법
- 문제에서 M에서 Z로 가는 경로를 물어서 처음에는 DFS, BFS 같은 탐색으로 풀어야 할 것 같은 느낌이 강하게 들었으나, 생각을 하다보니 그래프 탐색으로 풀려면 복잡할 것 같습니다.
- 유럽의 크기가 $25 \times 25$이므로
과감하게이차원 배열 탐색을 시도했습니다. - 모든 칸을 방문하면서 공백(’.’) 문자를 발견하면 주변 십자가 모양으로 네 칸을 확인합니다.
- 만약 주변 네 칸이 모두 블록 또는 시작/도착 지점이라면
- 그 외 경우는 주변 네 칸 중 파이프가 있는 두 칸을 보고 이어줍니다.
코드
1public class Main {
2
3 public static void main(String[] args) throws IOException {
4 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
5 StringBuilder sb = new StringBuilder();
6
7 String[] RC = br.readLine().split(" ");
8 int R = Integer.parseInt(RC[0]);
9 int C = Integer.parseInt(RC[1]);
10
11 char[][] map = new char[R][C];
12 for (int r = 0; r < R; r++) {
13 map[r] = br.readLine().toCharArray();
14 }
15
16 loop: for (int i = 0; i < R; i++) {
17 for (int j = 0; j < C; j++) {
18 if (map[i][j] != '.') continue;
19
20 boolean u = i - 1 < 0 ? false : "|+14MZ".contains(map[i - 1][j] + "");
21 boolean d = i + 1 >= R ? false : "|+23MZ".contains(map[i + 1][j] + "");
22 boolean l = j - 1 < 0 ? false : "-+12MZ".contains(map[i][j - 1] + "");
23 boolean r = j + 1 >= C ? false : "-+34MZ".contains(map[i][j + 1] + "");
24
25 char block = 0;
26 if (u && d && l && r){
27 if ("MZ".contains(map[i-1][j] + "") && "MZ".contains(map[i+1][j] + "")) block = '-';
28 else if ("MZ".contains(map[i][j - 1] + "") && "MZ".contains(map[i][j+1] + "")) block = '|';
29 else if ("MZ".contains(map[i][j - 1] + "") && "MZ".contains(map[i - 1][j] + "")) block = '1';
30 else if ("MZ".contains(map[i][j - 1] + "") && "MZ".contains(map[i + 1][j] + "")) block = '2';
31 else if ("MZ".contains(map[i][j + 1] + "") && "MZ".contains(map[i + 1][j] + "")) block = '3';
32 else if ("MZ".contains(map[i][j + 1] + "") && "MZ".contains(map[i - 1][j] + "")) block = '4';
33 else block = '+';
34 }
35 else if (u && l) block = '3';
36 else if (u && d) block = '|';
37 else if (u && r) block = '2';
38 else if (l && d) block = '4';
39 else if (l && r) block = '-';
40 else if (d && r) block = '1';
41
42 if (block == 0) continue;
43 sb.append(String.format("%d %d %c\n", i + 1, j + 1, block));
44 break loop;
45 }
46 }
47 System.out.println(sb);
48 }
49}
결과
첫 시도에는 질문 글에 있는 Counter example을 놓쳐 실패했습니다. 제출하기 전 조금 더 다양한 케이스를 고민하는 습관을 들여야겠다고 생각했습니다. 이 문제를 그래프 탐색으로 구현하더라도 코드가 크게 바뀌지는 않을 것 같습니다.
- 2차원 배열 탐색 대신 M의 좌표부터 바로 시작할테고,
- 문제에서 시작점과 종료 지점은 하나의 블록만 인접해 있다고 했으니 따라가면 될 것입니다.
- 파이프 블록을 따라가다 블록을 만나면 위 코드와 동일하게 사방의 파이프 블록을 확인할 것이고
- 문제에서 없어진 블록을 추가하면 모든 블록에 가스가 흐르게 된다고 했으므로 파이프 블록 연결 후 바로 탐색 종료하도록 구현하면 될 것 같습니다.
Prerequisites: 이 글에서 언급되었으나 깊게 설명하지 않은 내용입니다.
Comments