[백준] 11967 불켜기 - BFS(너비우선탐색) JAVA

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

11967번: 불켜기

코드설명

BFS(너비우선탐색) 를 활용하는 문제입니다.

 

코드로직에 대해 설명해보겠습니다.

 

1. ArrayList[][] map으로 각 지점마다 킬 수 있는 불의 위치를 저장합니다.

2. lightOn : 불이 켜졌는지 확인하는 배열입니다. 이를 통해 불이 켜진 배열만 방문하도록 도움을 받습니다.

3. alreadyLightUsed : 이미 해당 부분에서 불을 켰는지 확인하는 배열, 이를 통해 새로 방문했을때 이미 불을 킨 경험이 잇다면 해당 불을 켜도 결과는 변동이 없으므로 불필요 연산을 줄이기 위해 사용합니다.

4. visited : 해당 턴에서 방문한적 있는지 처리하는 배열입니다. 각 불이 켜졌는지 안켜졌는지에 따라서 방문할 수 있는 공간을 초기화해줘야합니다. 이때, 만약 해당 공간에서 새로 불이 켰다면, 해당 visited를 새로 초기화하여 새로 방문할 수 있는곳을 BFS를 통해 계속해서 방문할 수 있도록 처리합니다.

 

문제에서 가장 중요한점은, "불이 켜지면" BFS를 통해 새로 방문처리하여야한다는 점을 이해하는 것 입니다.

코드

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 {
	public static int N, M, P;
	public static ArrayList<Node>[][] map;
	public static int answer = 0;
	public static boolean[][] lightOn; //불켜졌는지 확인하는 배열입니다.
	public static boolean[][] alreadyLightUsed; //이미 해당 부분에서 불을 켰는지 확인하는 배열입니다.
	public static boolean[][] visited;
    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());
    	M = Integer.parseInt(st.nextToken());
    	
    	map = new ArrayList[N][N];
    	lightOn = new boolean[N][N];
    	alreadyLightUsed = new boolean[N][N];
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<N;j++) {
    			map[i][j] = new ArrayList<Node>();
    		}
    	}
    	
    	
    	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());
    		
    		map[x-1][y-1].add(new Node(a-1, b-1));
//    		System.out.println("X:"+x+ y+ a + b);
    	}
    	
    	simulate();
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<N;j++) {
    			if(lightOn[i][j] == true)
    				answer += 1;
    		}
    	}
    	
    	System.out.println(answer);
    	
    }
    
    public static void simulate() {
    	Queue<Node> q = new LinkedList<>();
    	q.offer(new Node(0, 0));
    	lightOn[0][0] = true;
    	int[] dx= {-1,1,0,0};
    	int[] dy = {0,0,-1,1};
    	
        while(!q.isEmpty()) {
            Node temp = q.poll();
            if(alreadyLightUsed[temp.r][temp.c] == false) {
                visited = new boolean[N][N];

                for(int i = 0; i<map[temp.r][temp.c].size(); i++) {
                    Node nodeLight = map[temp.r][temp.c].get(i); 
                    lightOn[nodeLight.r][nodeLight.c] = true;
                }
                alreadyLightUsed[temp.r][temp.c] = true;
                visited[temp.r][temp.c] = true;
            }

            for(int dir = 0; dir < 4; dir++) {
                int nr = temp.r + dx[dir];
                int nc = temp.c + dy[dir];

                if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                if( visited[nr][nc] == true) continue;
                if( lightOn[nr][nc] == false ) continue; //불이 켜진곳만 접근가능합니다.
                visited[nr][nc] = true;
                q.offer(new Node(nr, nc));
            }

        }
    	
    	
    }
    
}

class Node{
	int r;
	int c;
	public Node(int r, int c) {
		this.r = r;
		this.c = c;
	}
}