[JAVA] 백준 11967 : 불켜기

문제

11967번: 불켜기

 

해결 방법

루모스 ~

기본적인 탐색 문제에서 불을 켜고, 불이 켜진 방만 이동이 가능한 조금 응용된 문제이다.

각 방에 있는 스위치를 나타내기 위해서 ArrayList 배열을 사용해서 리스트에 불을 켤 수 있는 곳의 좌표를 넣어 두었고,

light와 visit을 활용해서 불이 켜져 있는지 여부와 방문 여부를 체크하였다.

 

탐색은 BFS를 사용했는데 불을 켤 수 있는 방이 존재하는지 여부는 리스트가 비었는지 체크해서 확인하였고,

비어있지 않다면 해당하는 칸에서 켤 수 있는 스위치를 통해 불을 켜주었고, 횟수만큼 결괏값을 증가시켰다.

그리고 스위치를 통해 불을 다 켰다면 리스트를 초기화 시켜 다시 스위치를 작동시키지 않게 하였다.

 

또 예제 입력에서 볼 수 있듯이 다른 칸에서 같은 칸의 스위치를 켤 수 있는데, 그렇기 때문에 이미 불이 켜진 곳은 다시 확인하지 않도록 설정해두어야 한다.(예제 입력에서는 [1, 1]에서 [1, 2]의 스위치를 작동시킬 수 있고 [1, 3]에서도 [1, 2]의 스위치를 작동시킬 수 있다.)

 

그리고 여기서 중요한게 (1, 1)에서 출발할 때는 (1, 4)가 불이 꺼져있어 갈 수 없었지만 (1, 2)를 거쳐 (1, 3)까지 이동한 후 (1, 3)에서 (1, 4)의 스위치를 작동시켜 불을 켤 수 있다면 다시 (1, 1)까지 돌아와서 (1, 4)를 방문해야 한다.그래서 스위치를 작동시킬 수 있을 때마다 visit 배열을 초기화시켜 방문할 수 있게 하였다.

 

result가 1로 초기화된 이유는 (1, 1)의 불이 켜진 상태로 시작하기 때문이다.

 

코드

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 Main {
	static int dx[] = {0, 0, -1, 1};
	static int dy[] = {-1, 1, 0, 0};
	
	static int N;
	static ArrayList<Room> shed[][];
	static boolean light[][];
	static boolean visit[][];
	static int result = 1;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        shed = new ArrayList[N + 1][N + 1];
        light = new boolean[N + 1][N + 1];
        visit = new boolean[N + 1][N + 1];
        
        for (int i = 1; i <= N; i++) {
        	for (int j = 1; j <= N; j++) {
        		shed[i][j] = new ArrayList<>();
        	}
        }
        
        for (int i = 0; i < M; i++) {
        	st = new StringTokenizer(br.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());
        	
        	shed[x][y].add(new Room(a, b));
        }
        
        bfs();
        System.out.println(result);
    }
    
    static void bfs() {
    	Queue<Room> q = new LinkedList<>();
    	q.offer(new Room(1, 1));
    	light[1][1] = true;
    	visit[1][1] = true;
    	
    	while(!q.isEmpty()) {
    		Room temp = q.poll();
    		
    		// 불을 켤 수 있는 방이 있다면 전부 켜줌
    		if (!shed[temp.x][temp.y].isEmpty()) {
    			// 방문을 초기화 해서 다시 방문 해줌
    			visit = new boolean[N + 1][N + 1];
    			visit[temp.x][temp.y] = true;
    			for (Room room : shed[temp.x][temp.y]) {
    				// 불이 켜져있지 않은 방만 켜줌
    				if (!light[room.x][room.y]) {
    					light[room.x][room.y] = true;
        				result++;
    				}
    			}
    			// 켤 수 있는 곳을 다 켰기 때문에 없애줌
    			shed[temp.x][temp.y].clear();
    		}
    		
    		for (int i = 0; i < 4; i++) {
    			int newX = temp.x + dx[i];
    			int newY = temp.y + dy[i];
    			
    			if (newX <= 0 || newY <= 0 || newX > N || newY > N) continue;
    			
    			if (light[newX][newY] == true && !visit[newX][newY]) {
    				// 불이 켜져있고 방문을 하지 않았으면 방문
    				q.offer(new Room(newX, newY));
    				visit[newX][newY] = true;
    			}
    		}
    	}
    }
}

class Room {
	int x;
	int y;
	
	Room (int x, int y) {
		this.x = x;
		this.y = y;
	}
}