[백준] 11967. 불켜기
문제 링크
풀이 과정
전에 풀었던 문제 [백준] 9328. 열쇠 의 접근 방식과 유사하게 풀었습니다.
아이디어는 다음과 같습니다.
- 다음 방에 전구가 꺼져있어 이동하지 못한다면, candidates 라는 Set에 담아둔다.
- 새로운 방에 들어왔을 때, 켤 수 있는 전구들을 모두 켜고, 여기서 켤 수 있는 전구들이 예전에 불이 꺼져있어 가지 못한 방이라면 큐에 넣어준다.
Switch[][] map = new Switch[N][N];
boolean[][] visit = new boolean[N][N];
boolean[][] on = new boolean[N][N];
HashSet<Point> candidates = new HashSet<>();
int answer = 1;
사용된 핵심 변수들은 위와 같습니다.
- map 은 각 좌표에 존재하는 스위치들을 담아두는 2차원 배열입니다. Switch 객체 내부엔 스위치 좌표가 ArrayList로 담겨 있습니다.
- visit 은 각 좌표에 방문 여부를 처리하는 배열입니다.
- on 은 각 좌표에 해당하는 방에 불이 켜져있는 지 여부를 저장하는 배열입니다.
- candidates 는 위치상 도달할 수 있지만, 불이 꺼져 있어 들어가지 못한 방들의 좌표를 담고 있습니다. 나중에 여기 담겨 있는 방이었는 지 확인을 위해 HashSet 으로 선언했습니다.
- answer 는 불을 켤 수있는 방의 개수를 담는 변수입니다. 초기 (0, 0) 위치는 불이 켜져 있다는 문제 조건에 따라, 초기 값을 1로 설정했습니다.
while (M-- > 0) {
st = new StringTokenizer(br.readLine());
int x, y, a, b;
x = stoi(st.nextToken()) - 1;
y = stoi(st.nextToken()) - 1;
a = stoi(st.nextToken()) - 1;
b = stoi(st.nextToken()) - 1;
map[x][y].switches.add(new Point(a, b));
}
입력 x, y, a, b는 (x, y) 방에서 (a, b) 방의 불을 켤 수 있다는 의미입니다. 입력받음과 동시에 (x, y)의 요소로 존재하는 객체의 switches 라는 이름의 ArrayList에 추가합니다.
Queue<Point> queue = new LinkedList<>();
on[0][0] = true;
visit[0][0] = true;
queue.add(new Point(0, 0));
큐를 생성한 뒤, (0, 0) 방엔 불이 켜져 있으니, on 과 visit 배열을 처리한 뒤에 큐에 담아 둠으로써, BFS 탐색을 준비합니다.
while (!queue.isEmpty()) {
Point now = queue.poll();
for (Point next : map[now.x][now.y].switches) {
if (!on[next.x][next.y]) {
on[next.x][next.y] = true;
answer++;
if (candidates.contains(next)) {
queue.add(next);
}
}
}
for (int d = 0; d < 4; d++) {
int nx = now.x + dx[d], ny = now.y + dy[d];
if (!isInRange(nx, ny) || visit[nx][ny]) continue;
if (!on[nx][ny]) {
candidates.add(new Point(nx, ny));
continue;
}
visit[nx][ny] = true;
queue.add(new Point(nx, ny));
}
}
BFS 탐색은 다음과 같이 진행됩니다.
- 큐에서 꺼낸 now 라는 이름의 변수가 담고 있는 좌표에 달려있는 스위치들을 확인하며, 켜지지 않았으면 불을 켜고, 해당 좌표가 candidates 에 존재한다면 큐에 넣어줍니다.
- 어떤 좌표가 candidates 에 존재한다면, 예전에 도달할 수 있었지만 불이 꺼져 있어 더 이상 진행을 하지 못한 방을 의미합니다. 방금 불을 켰고, 이로 인해 BFS 탐색이 가능해졌으므로, 해당 좌표를 큐에 넣어 그 좌표로부터의 탐색을 추가로 시도합니다.
- 다음 방 불이 꺼져 있다면, 해당 방이 나중에 불이 켜질 수 있으므로 candidates 에 담아주고 다음을 기약합니다.
- 다음 방 불이 켜져 있다면, 방문처리 한 후 큐에 넣어 탐색을 계속 합니다.
코드
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = stoi(st.nextToken());
int M = stoi(st.nextToken());
Switch[][] map = new Switch[N][N];
boolean[][] visit = new boolean[N][N];
boolean[][] on = new boolean[N][N];
HashSet<Point> candidates = new HashSet<>();
int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
int answer = 1;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
map[i][j] = new Switch();
while (M-- > 0) {
st = new StringTokenizer(br.readLine());
int x, y, a, b;
x = stoi(st.nextToken()) - 1;
y = stoi(st.nextToken()) - 1;
a = stoi(st.nextToken()) - 1;
b = stoi(st.nextToken()) - 1;
map[x][y].switches.add(new Point(a, b));
}
Queue<Point> queue = new LinkedList<>();
on[0][0] = true;
visit[0][0] = true;
queue.add(new Point(0, 0));
while (!queue.isEmpty()) {
Point now = queue.poll();
for (Point next : map[now.x][now.y].switches) {
if (!on[next.x][next.y]) {
on[next.x][next.y] = true;
answer++;
if (candidates.contains(next)) {
queue.add(next);
}
}
}
for (int d = 0; d < 4; d++) {
int nx = now.x + dx[d], ny = now.y + dy[d];
if (!isInRange(nx, ny) || visit[nx][ny]) continue;
if (!on[nx][ny]) {
candidates.add(new Point(nx, ny));
continue;
}
visit[nx][ny] = true;
queue.add(new Point(nx, ny));
}
}
System.out.println(answer);
}
static class Switch {
ArrayList<Point> switches = new ArrayList<>();
}
static boolean isInRange(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N;
}
static int stoi(String s) {
return Integer.parseInt(s);
}
}
댓글남기기