[BOJ] 11967. 불켜기

간단한 BFS 문제 같지만 방문고려요소가 상당히 많은 문제이다.

방문을 위한 조건이 1. 현재방에서 인접한 방이고 2. 불이 켜져있어야 함으로 배열을 near,light,visit로 세가지를 만들었다. 그리고 0,0에서 시작 후 첫번째로 near를 이용하여 근접한 방을 체크해주었고, 두번째로 현재방에서 불을 킬수있는 방을 불을 키면서 near이면 queue에 넣어주었다. 그후 세번째로 현재방에서 다시 근접한 불켜진 방들을 방문하였다. 이러한 방식을 이용하여 BFS를 돌면서 불을 켜주는 과정을 반복하였다.

문제가 상당히 접근이 어려워서 도움을 받아 풀게되었다. 다시 풀어볼 필요가 있는 문제같다.

package boj2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_11967_불켜기 {
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    
    static int N,M;
    
    static List<Integer>[] move;
    
    static boolean[][] near;
    static boolean[][] visit;
    static boolean[][] light;
    
    static Queue<Pos> queue;
    
    static class Pos{
        int i,j;
        Pos(int i,int j){
            this.i=i;this.j=j;
        }
    }
    
    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());
        M=Integer.parseInt(st.nextToken());
        
        move=new ArrayList[N*N];
        for(int i=0;i<N*N;i++) {
            move[i]=new ArrayList<>();
        }
        
        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;
            
            move[x*N+y].add(a*N+b);
        }
        
        near=new boolean[N][N];
        visit=new boolean[N][N];
        light=new boolean[N][N];
        queue=new LinkedList<>();
        bfs();
        
        int answer=0;
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(light[i][j]==true)
                    answer+=1;
//                System.out.print(light[i][j]?"1 ": "0 ");
            }
//            System.out.println();
        }
        
        System.out.println(answer);
    }
    
    static void bfs() {
        near[0][0]=true;
        visit[0][0]=true;
        light[0][0]=true;
        queue.add(new Pos(0, 0));
        
        while(!queue.isEmpty()) {
            Pos cur= queue.poll();
            
            //근처 이동가능
            for(int dir=0;dir<4;dir++) {
                int nextI=cur.i+di[dir];
                int nextJ=cur.j+dj[dir];
                if(nextI<0 || nextI>=N || nextJ<0 ||nextJ>=N)
                    continue;
                
                near[nextI][nextJ]=true;
            }
            
            //불키기
            for(int next : move[cur.i*N + cur.j]) {
                light[next/N][next%N]=true;
                
                if(near[next/N][next%N]==true && light[next/N][next%N]==true 
                        && visit[next/N][next%N]==false) {
                    visit[next/N][next%N]=true;
                    queue.offer(new Pos(next/N, next%N));
                }
            }
            
            //근처 이동
            for(int dir=0;dir<4;dir++) {
                int nextI=cur.i+di[dir];
                int nextJ=cur.j+dj[dir];
                if(nextI<0 || nextI>=N || nextJ<0 ||nextJ>=N)
                    continue;
                if(near[nextI][nextJ]==true && light[nextI][nextJ]==true 
                        && visit[nextI][nextJ]==false) {
                    visit[nextI][nextJ]=true;
                    queue.offer(new Pos(nextI, nextJ));
                }
            }
        }
    }
    
}