[백준] 불켜기 11967번 (java)

코드

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

 

풀이 방법

불 켜진 방으로만 이동이 가능하다.

불이 켜진 방으로 이동한 후, 켤 수 있는 불을 모두 킨다.

불을 켤 때, 주변에 방문한 곳이 있다면 해당 방도 방문할 수 있기 때문에 queue에 넣어준다.

또한 방에 방문했을 때, 주변에 방문을 하지 않았지만, 불이 켜진 방이 있다면 해당 방도 queue에 넣어준다.

 

코드

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {    

    public static ArrayList<int[]>[][] switches;
    public static boolean[][] visited;
    public static boolean[][] onLight;

    public static int[] dy = {0, 0, -1, 1};
    public static int[] dx = {1, -1, 0, 0};
    public static int N, ans = 1;
    public static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {0, 0});
        visited[0][0] = true;
        onLight[0][0] = true;
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            
            // 방문 했을 때 불 다 켜기
            for (int i = 0;i < switches[cur[0]][cur[1]].size();i++) { 
                int[] light = switches[cur[0]][cur[1]].get(i);
                if (onLight[light[0]][light[1]] == false) ans++;
                onLight[light[0]][light[1]] = true;
                if (visited[light[0]][light[1]]) continue;
                for (int k = 0;k < 4;k++) {
                    int ny = light[0] + dy[k];
                    int nx = light[1] + dx[k];
                    if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
                    if (visited[ny][nx] == true) {
                        q.add(new int[] {light[0], light[1]});                        
                        visited[light[0]][light[1]] = true;
                    } 
                }
            }
            
            for (int i = 0;i < 4;i++) {
                int ny = cur[0] + dy[i];
                int nx = cur[1] + dx[i];
                if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
                if (visited[ny][nx]) continue;
                if (!onLight[ny][nx]) continue;
                q.add(new int[] {ny, nx});
                visited[ny][nx] = true;                
            }
            
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 첫 줄 입력: N, M
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        visited = new boolean[N][N];
        onLight = new boolean[N][N];
        // 스위치 정보 저장
        switches = new ArrayList[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                switches[i][j] = new ArrayList<>();
            }
        }

        // 다음 M줄 입력
        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());

            switches[y-1][x-1].add(new int[]{b-1, a-1});
        }

        bfs();

        System.out.println(ans);
    }
}