[백준 11967 - Java] 불켜기

https://www.acmicpc.net/problem/11967

11967번: 불켜기

 

문제

농부 존은 최근에 N*N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2≤N≤100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.

베시는 유일하게 불이 켜져있는 방인 (1,1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다. 

베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.

입력

첫 번째 줄에는 N(2≤N≤100)과, M(1≤M≤20,000)이 정수로 주어진다.

다음 M줄에는 네 개의 정수 x, y, a, b가 주어진다. (x, y)방에서 (a, b)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다. 

출력

베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오.

 

풀이

 

저는 Room이라는 객체를 만들어서 ArrayList 2차원 배열로 만들어 불을 켤 수 있는 방들을 표시하는데에 사용하였습니다.

그런 뒤 BFS를 사용해서 이동해가며 방에 불을 켜고 또 불이 켜진 곳 중 이동 가능한 위치들로 이동하며 불을 켤 수 있는 방을 모두 찾는 방식으로 구현하였습니다.

이 때 중요한 것은 이미 방문하려 했으나 불이 꺼져있던 곳이 나중엔 불이 켜져서 방문이 가능해지는 경우를 처리해야하는데요. 이를 위해서 이동이 가능한 모든 위치들을 canMove라는 이차원 배열에 표시하여 후에 사용해 주었습니다.

 

import java.util.Scanner;
import java.util.*;

public class Main {
	static int N, M;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);	
		N = sc.nextInt();
		M = sc.nextInt();
		
		int cnt = 0;
		ArrayList<Room> [][] arr = new ArrayList[N+1][N+1];
		Queue<Room> q = new LinkedList<>();
		int[][] visited = new int[N+1][N+1];
		int[][] light = new int[N+1][N+1];
		int[] X = {1, -1, 0, 0};
		int[] Y = {0, 0, 1, -1};
		
		for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                arr[i][j] = new ArrayList<>();
            }
        }
		
		for(int i=0; i<M; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			int a = sc.nextInt();
			int b = sc.nextInt();
			arr[x][y].add(new Room(a, b));
		}
		
		q.add(new Room(1, 1));

		light[1][1] = 1;
		cnt++;
		// 이동 가능한 지점들 표시 
		int[][] canMove = new int[N+1][N+1];
		
		while(!q.isEmpty()) {
			Room now = q.poll();
			
			visited[now.x][now.y] = 1;
			
			//불 켜기 
			for(Room r : arr[now.x][now.y]) {
				if(light[r.x][r.y]== 1)
					continue;
				light[r.x][r.y]= 1;
				cnt++;
				if(canMove[r.x][r.y] == 1)
					q.add(new Room(r.x, r.y));
				
			}
			
			for(int i=0; i<4; i++) {
				int nextX = now.x+X[i];
				int nextY = now.y+Y[i];
				if(nextX<1 || nextX>N || nextY<1 || nextY>N)
					continue;
				
				canMove[nextX][nextY] = 1;
				
				//이미 방문했거나 불꺼진 방 
				if(visited[nextX][nextY] == 1 || light[nextX][nextY] == 0)
					continue;
				
				q.add(new Room(nextX, nextY));
			}
		}
		System.out.println(cnt);
		
	}
	
	static class Room {
		int x, y;
		
		Room (int x, int y){
			this.x = x;
			this.y = y;
			
		}
	}

}