[BOJ]1967号:点灯(JAVA)

質問する (Gold 3)

11967：点灯

に答える

いつどこで探索するかが重要な問題です!
まず、ステータスが変更されないまでブラウズを繰り返します.

ナビゲーションコード

倉oTMP:探索前の状態を保存します.

でナビゲートした場所で、スイッチを入れられる場所のchango値をtrueに変更します.

BFSナビゲーションを回し、ナビゲートした場所で地図上のリストを回し、スイッチ

を開き続けます.

探索戦とは異なる状態であれば、新しい場所があることを意味します!
つまり、もう一度探索する必要があるので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回解けば成功!
最初は探索が終わると結果が出力される->正しいコードは不可能...ははは