[Baekjoon] 11967_불켜기

Gold II

문제(출처: https://www.acmicpc.net/problem/11967)

---

< 불켜기 >

 

문제 풀이 

 

먼저 (1,1) 방에서 스위치를 통해 다른 방 불을 켠다. 불이 켜진 방에서 상하좌우를 탐색하여 다른 방과 연결되어 있는지 확인한다. 다른 방과 연결되어 있다면 이 방에도 올 수 있다는 뜻이 된다. 하지만 다른 방과 연결되어 있지 않다면 이 방은 불만 켤 수 있고 이 방과 연결된 스위치는 조절할 수 없다. 

 

이렇게만 탐색을 할 경우 다른 방에 의해 불이 켜진 방을 갈 수 있는지 없는지 확인할 수 없으므로 현재 방에서 상하좌우를 탐색해 다른 방으로 이동 가능한지 한번 더 판단한다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _11967_ { // 불켜기
	static boolean visited[][];
	static Room[][] arr;
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };

	static class Room {
		private boolean light;
		private ArrayList<int[]> link;

		public Room(Boolean light, ArrayList<int[]> link) {
			this.light = light;
			this.link = link;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		arr = new Room[n + 1][n + 1];
		visited = new boolean[n + 1][n + 1];

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				arr[i][j] = new Room(false, new ArrayList<>());
			}
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			arr[x][y].link.add(new int[] { a, b });
		}

		arr[1][1].light = true;
		visited[1][1] = true;

		System.out.println(bfs(1, 1));
	}

	private static int bfs(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x, y });

		int result = 1;

		while (!queue.isEmpty()) {
			int pos[] = queue.poll();

			for (int[] num : arr[pos[0]][pos[1]].link) {
				if (!arr[num[0]][num[1]].light) {
					result += 1;
					arr[num[0]][num[1]].light = true;

					for (int i = 0; i < 4; i++) {
						int a = num[0] + dx[i];
						int b = num[1] + dy[i];

						if (a >= 1 && a < arr.length && b >= 1 && b < arr.length && visited[a][b]) {
							visited[num[0]][num[1]] = true;
							queue.add(new int[] { num[0], num[1] });
							break;
						}
					}
				}
			}

			for (int i = 0; i < 4; i++) {
				int a = pos[0] + dx[i];
				int b = pos[1] + dy[i];

				if (a >= 1 && a < arr.length && b >= 1 && b < arr.length && arr[a][b].light && !visited[a][b]) {
					visited[a][b] = true;
					queue.add(new int[] { a, b });
				}
			}
		}
		return result;
	}
}

변수)
visited : 방문 여부
arr : 각 좌표에 해당하는 방의 정보를 저장 
dx, dy : 상하좌우
n, m : N x N, 방 정보
x, y, a, b : (x, y) 방에서 (a, b) 방의 불을 켜고 끌 수 있음

 

Room

불 켜짐 여부와 현재 방에서 불을 켜고 끌 수 있는 방 좌표를 저장

 

Main

n과 m을 입력받은 후 먼저 NxN 크기만큼 배열을 만들어 초기화한다. m 줄 만큼 방 정보를 입력받아 arr 배열에 정보를 저장한다. (1,1)부터 시작하므로 방 불을 켜고, 방문 표시를 한 후 bfs 함수를 호출한 후 그 결과를 출력한다.

 

bfs (x좌표, y좌표)

(1,1) 위치부터 시작하기 위해 queue에 추가하며 (1,1) 방도 정답에 포함하므로 초기 result를 1로 선언한다. 

queue가 빌 때까지 반복한다. queue에서 값을 하나 뽑아와 이 방에서 조절할 수 있는 방들의 불을 켜고, result도 +1 한다. 방들의 불을 켜면서 새로 불이 켜진 방들의 위치에서 상하좌우를 탐색해 다른 방을 이미 방문한 적이 있다면 새로 불이 켜진 방도 방문할 수 있으므로 방문 표시 후 queue에 추가한다.

 

현재 위치에서 상하좌우를 탐색해 불이 켜진 방이지만 아직 방문하지 않은 곳을 찾아 방문한다.

 

최종 reuslt를 반환한다.

---

---