풀이
bfs문제인데, 정말 재밌게 풀은 문제이다.
요약하자면 bfs가 맞긴 한데, 특정 조건 하에 계속 bfs를 다시 처음부터 돌려주는 것이 이 문제의 핵심이다.
그 이유는, 일반적인 bfs()라면 방문배열을 사용하기 때문에 지나온 칸으로 다시 돌아갈 수 없다. 그런데 이 문제에서보면, 예제의 힌트에서 “(1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으므로, (2, 3)위치에 있는 스위치는 누를 수 없다. 그러므로 불을 밝힐 수 있는 방의 최대 개수는 5이다.” 라고 말하고 있다. 즉, (2,1)로 가려면 지나왔던 칸을 다시 가서 (1,1)로 돌아간 다음에 (2,1)로 가는 것이다. 그런데 지나왔던 칸을 돌아가려면 visited를 없애야한다. 근데 visited를 없애면 무한 루프에 빠지게 되므로, 한번의 bfs()에서 불을 켤 수 있는 곳을 최대한 켜놓고, 다시 1,1부터 bfs를 하게 되는 것이다. 그리고 이 bfs가 멈추는 조건은 새롭게 스위치를 켠 방이 없는 것이다. 이 문제에서는 스위치를 최대로 켤 수 있는 개수를 구하는 것이기 때문에, 더이상 스위치를 켤 수 없다면, 그게 정답이다.
필자가 방문 배열을 없앴다가 무한 루프를 도는 것을 보고 아차 싶었던 사람이기 때문에 설명을 위와 같이 했다.
풀이 과정은 아래와 같다.
- 준비물
- 불을 켤 수 있는 스위치가 있는 칸을 저장하는 2차원 배열 = ArrayList[][]
- bfs용 Queue
- bfs 한번 할 때 체크할 방문 배열 = visited
- 불이 켜진 곳인이 켜지지 않은 곳인이 표시한 2차원 배열 = int[][]
- 풀이 과정
- 불을 켤 수 있는 스위치를 저장한다.
- bfs()
- 현재 bfs에서 불을 켠 횟수 초기화 = cnt
- 방문 배열, 큐 초기화
- 새로운 방에 불이 켜졌는지 안켜졌는지 확인할 수 있는 변수 = flag
- 베시가 (1,1)에서 출발하므로, visited[1][1] = true를 하고, q에 (1,1)삽입
- 탐색 시작(while)
- 현재 위치 = q.poll()
- 현 위치에서 불을 켤 수 있는 스위치가 있는지 확인한 후, 있다면 불을 켜고, flag = true로 바꿔준다.
- 다음 위치로 이동하기 위해 조건에 맞는 칸이라면 q에 삽입한다. 이동 조건은 불이 켜진 칸이여야 하고, 현재 bfs()에서 방문한 적이 없는 칸이다.
- 모든 탐색이 끝나면, 이번 bfs()에서 새로운 방에 불이 켜졌는지 확인해서, 불을 켰다면 새로운 bfs()를 시작한다.
- 불을 켠 스위치의 개수를 return하며 bfs()종료
- bfs()에서 불을 켰던 스위치의 개수는 초기에 불이 켜져있던 (1,1)을 계산하지 않은 값이므로 +1을 하여 정답으로 출력한다.
소스 코드
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
import java.util.*;
public class 불켜기 {
static int n, m;
static int[][] map;
static boolean[][] visited;
static ArrayList<int[]>[][] light;
static Queue<Point> q;
static int[] dx = {1,-1,0,0};
static int[] dy = {0,0,-1,1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
map = new int[n+1][n+1];
light = new ArrayList[n+1][n+1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
light[i][j] = new ArrayList<>();
}
}
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
int d = sc.nextInt();
light[a][b].add(new int[] {c,d});
}
map[1][1] = 1;
int result = bfs();
System.out.println(result+1);
}
static int bfs() {
int cnt = 0;
visited = new boolean[n+1][n+1];
q = new LinkedList<>();
q.add(new Point(1,1));
boolean flag = false;
visited[1][1] = true;
while (!q.isEmpty()) {
Point now = q.poll();
for (int[] turnOn : light[now.r][now.c]) {
if (map[turnOn[0]][turnOn[1]] == 0) {
map[turnOn[0]][turnOn[1]] = 1;
flag = true;
cnt++;
}
}
for (int i = 0; i < 4; i++) {
int nr = now.r+dx[i];
int nc = now.c+dy[i];
if (nr >= 1 && nc >= 1 && nr <= n && nc <= n) {
if (map[nr][nc] == 1 && !visited[nr][nc]) {
visited[nr][nc] = true;
q.add(new Point(nr, nc));
}
}
}
}
if (flag)
cnt += bfs();
return cnt;
}
static class Point{
int r;
int c;
public Point(int r, int c) {
this.r = r;
this.c = c;
}
}
}
태클 감사합니다.
조언 환영입니다.