[BOJ] 11967번: 불켜기 (JAVA)

문제 (Gold 3)

11967번: 불켜기

풀이

탐색을 언제, 어디에서 하는지가 굉장히 중요한 문제!

우선, 더 이상 상태 변경이 없을 때까지 탐색을 반복한다.

탐색 코드

1. cangoTmp: 탐색하기 전의 상태를 저장해 놓는다.
2. 탐색한 곳에서 스위치를 켤 수 있는 곳의 cango값을 true로 변경한다.
3. BFS 탐색을 돌고, 탐색한 곳에서 map의 List를 돌며 계속해서 스위치를 켠다
4. 탐색 전과 다른 상태라면, 새로 갈 수 있는 곳이 생겼다는 의미 !
   즉, 한번 더 탐색을 해야하므로 true를 리턴한다. 

코드

package graphTraversal;

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

public class BOJ_11967_불켜기 {
    static int[] di = {-1, 0, 1, 0};
    static int[] dj = {0, -1, 0, 1};
    static int N;
    static List<int[]>[][] map; // 연결되어 있는 스위치 정보들을 List로 저장
    static boolean[][] cango;
    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());
        map = new List[N][N];
        cango = new boolean[N][N];
        for(int i =0 ; i < N ; i++)
            for(int j =0 ; j < N ; j++)
                map[i][j] = new ArrayList<>();

        for(int i =0 ; i < M ; i++){
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken())-1;
            int y1 = Integer.parseInt(st.nextToken())-1;
            int x2 = Integer.parseInt(st.nextToken())-1;
            int y2 = Integer.parseInt(st.nextToken())-1;
            map[x1][y1].add(new int[]{x2, y2});
        }

        while(turnOn()){}       // 더이상 상태 변경이 없을 때까지 탐색 지속

        int cnt = 0;
        for(int i =0 ; i < N ; i++){
            for(int j =0 ;j < N ; j++){
                if(cango[i][j]) cnt++;
            }
        }
        System.out.println(cnt);
    }

    private static boolean turnOn() {
        boolean[][] cangoTmp = new boolean[N][N];
        for(int i =0 ; i < N ; i++) cangoTmp[i] = Arrays.copyOf(cango[i], cango[i].length);
        Queue<int[]> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[N][N];
        q.offer(new int[]{0,0});
        visited[0][0] = true;
        cango[0][0] = true;
        for(int[] i : map[0][0]) cango[i[0]][i[1]] = true;
        while(!q.isEmpty()){
            int[] cur = q.poll();
            for(int d =0 ; d < 4 ; d++){
                int ni = cur[0] + di[d];
                int nj = cur[1] + dj[d];
                if(0<=ni&&ni<N && 0<=nj&&nj<N){
                    if(!visited[ni][nj] && cango[ni][nj]){
                        for(int[] i : map[ni][nj]) cango[i[0]][i[1]] = true;        // 스위치 켜기
                        visited[ni][nj] = true;
                        q.offer(new int[]{ni, nj});
                    }
                }
            }
        }

        // 탐색 전과 다른 상태라면, 한번 더 탐색을 해야함!
        for(int i =0 ; i < N ; i++){
            for(int j = 0 ; j < N ; j++){
                if(cangoTmp[i][j] != cango[i][j]) return true;
            }
        }
        return false;
    }
}

제출

제대로 풀어서 2트만에 성공!
처음엔 탐색이 한번 끝나면 바로 결과를 출력했다 -> 맞을 수가 없는 코드..ㅎ_ㅎ