백준 11967. 불켜기 :: 돼지개발자

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

"상태 공간에 대한 정확한 이해가 필요"

먼저 상태 공간에 대한 정의가 중요하다. 나는 방문 여부를 체크하는 visited와 해당 방에 불이 켜져있는지를 체크하는 light  두 개의 2차원 배열을 두었다. 그리고 방에 있는 스위치 정보는 x,y 좌표를 x*N +y 를 사용해 index로 변환해서 저장했다. 따라서 아래와 같은 변수를 사용한다.

ArrayList<Integer>[] list;

A 방에 도착해서 B 방에 불을 켰고 B까지 갈 수 있다면 가정했을 때, 그 방을 기점으로 해서 다시 탐색을 시작해야함을 주의한다. 나는 처음에 불을 다시 켰을 때 visited 배열을 초기화 시켰는데, 통과는 했으나 시간이 오래 걸려 그냥 q에 넣어주는식으로 구현함.

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 {
 
    static int N,M;
    static ArrayList<Integer>[] list;
    static boolean[][] visited;
    static boolean[][] light;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static Queue<Integer> q = new LinkedList<>();
    static int cnt;
    
    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());
        
        visited = new boolean[N][N];
        light = new boolean[N][N];
        
        list = new ArrayList [N*N];
        
        for (int i = 0; i < N*N; i++) {
            list[i] = new ArrayList<Integer>();
        }
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            list[x*N+y].add(a*N+b);
        }
        
        visited[0][0] = light[0][0] = true;
        q.add(0);
        
        while(!q.isEmpty()) {
            
            int cur = q.poll();
            int x = cur / N;
            int y = cur % N;
            turnOn(cur);
            
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(!isRange(nx, ny) || visited[nx][ny] || !light[nx][ny])
                    continue;
                
                int next = nx*N + ny;
                
                visited[nx][ny] = true;
                q.add(next);
            }
        }
        
        System.out.println(cnt+1);
    }
    
    static void turnOn(int idx) {
        for (int i = 0; i < list[idx].size(); i++) {
            int num = list[idx].get(i);
            int x = num / N;
            int y = num % N;
            
            if(light[x][y]) continue;
            
            light[x][y] = true;
            cnt++;
 
            // 만약 불이 켜진 방에 갈 수 있다면, 검색한다.
            for (int j = 0; j < 4; j++) {
                int nx = x + dx[j];
                int ny = y + dy[j];
                if(isRange(nx, ny) && visited[nx][ny]) {
                    q.add(nx*N + ny);
                    break;
                }
            }
        }
    }
    
    static boolean isRange(int x,int y) {
        if(x < 0 || x >= N || y < 0 || y >= N) return false;
        return true;
    }
}