[backjoon]11967번: 불켜기(java)

www.acmicpc.net/problem/11967

11967번: 불켜기

문제 풀이 방식은 위상 정렬 풀이 방식과 흡사하다고 생각했다.

간단한 순서가 있어서 ArrayList를 이용하여 값을 넣어준 후, 

BFS를 이용하여 풀이를 해주었다.

이 문제에서

1. 적절하게 값 넣기 (이 생각이 제일 어려웠음)

2. 문제를 잘 부분을 나눠서 꼼꼼하게 코딩하기 

이걸 잘 생각한다면 나름 평이한 문제라고 생각이 든다.

 

import java.io.*;
import java.util.*;
class Main {
	static int N, light;
	static ArrayList<Dot> room[][];
	static boolean[][] visit, turnOn, move;
	static int[][] dir = {{-1, 0},{1, 0},{0, -1},{0, 1}};
	
	public static void main(String[] args) throws Exception {
		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());
		
		visit = new boolean[N+1][N+1];
		turnOn = new boolean[N+1][N+1];
		move = new boolean[N+1][N+1];
		room = new ArrayList[N+1][N+1];
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				room[i][j] = new ArrayList<Dot>();
			}
		}
		
		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());
			room[x][y].add(new Dot(a, b));
			
		}
		bfs();
		System.out.println(light);
	}
	
	public static void bfs() {
		Queue<Dot> queue = new LinkedList<Dot>();
		queue.add(new Dot(1, 1));
		turnOn[1][1] = true;
		visit[1][1] = true;
		light = 1;
		
		while(!queue.isEmpty()) {
			
			Dot dot = queue.poll();
			
			//불을 켜는 부분.
			for (int j = 0; j < room[dot.row][dot.col].size(); j++) {
				Dot temp = room[dot.row][dot.col].get(j);
				if(turnOn[temp.row][temp.col]) continue;
				turnOn[temp.row][temp.col] = true;
				light++;
			}
			//켜진 방에 한해 돌아다닐 수 있는 곳을 확인(상하좌우)
			for (int i = 0; i < dir.length; i++) {
				int nextR = dot.row + dir[i][0];
				int nextC = dot.col + dir[i][1];
				
				if(nextR < 0 || nextC < 0 || nextR >N || nextC >N) continue;
				
				move[nextR][nextC] = true;//움직 일 수 있다.
			}
			//불이 켜져서 돌아다닐 수 있지만 순서상 못 간 곳도 있기 때문에 다시 돌면서 점검.
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					//불이 켜진 곳 && 움직일 수 있는 곳 && 방문하지 않은 곳
					if(turnOn[i][j] && move[i][j] && !visit[i][j]) {
						visit[i][j] = true;
						queue.add(new Dot(i, j));
					}
				}
			}
		}
	}
}
class Dot{
	int row;
	int col;
	Dot(int r, int c){
		row = r;
		col = c;
	}
}