[BFS] 백준 11967번 불켜기 - JAVA

 

 

 

 

---

1. 출처

---

 

 

11967번: 불켜기

 

 

 

---

2. 설계

---

 

 

 

문제 풀 때는 도저히 생각이 나지 않아서 어려웠는데 풀고 나니 별 것 아닌 문제이다.

BFS의 기본 구조만 알면 거기서 2가지 포인트만 추가해주면 되기 때문이다.

 

BFS의 기본 구조는 다음과 같다.

public static void BFS(){
    Queue<Location> q = new LinkedList<>();//갈 수 있는 경로
    q.offer(new Location(1,1));

    while(!q.isEmpty()){
        Location newLoc = q.poll();

        //다음으로 이동(큐에 넣기)
        for(int d=0;d<4;d++){
            int nextX = newLoc.x + drc[d][0];
            int nextY = newLoc.y + drc[d][1];

            if(nextX<0 || nextX>=N+1 || nextY<0 || nextY>=N+1) continue; //경계체크
            if(visited[nextX][nextY]) continue;
            
            visited[nextX][nextY] = true;
            q.offer(new Location(nextX, nextY));
        }
    }
  }

 

 

이 구조에서 추가되는 부분은 주석으로 (여기) 라고 표시하겠다.

 

이 기본 구조에 1) 불 켜주는 로직이 필요하다.

1 1 1 2 라고 하면 (1,1)에 도달했을 때 (1,2)의 불을 켤 수 있다는 의미이다.

public static void BFS(){
    Queue<Location> q = new LinkedList<>();
    q.offer(new Location(1,1));

    while(!q.isEmpty()){
        Location newLoc = q.poll();

        //불켜기 (여기)
        for(int i=0;i<map[newLoc.x][newLoc.y].size();i++){
            Location next = map[newLoc.x][newLoc.y].get(i);

            if(onoff[next.x][next.y]) continue; //이미 켜져있는 건 패스

            onoff[next.x][next.y] = true;
            result++;
        }

        for(int d=0;d<4;d++){
            int nextX = newLoc.x + drc[d][0];
            int nextY = newLoc.y + drc[d][1];

            if(nextX<0 || nextX>=N+1 || nextY<0 || nextY>=N+1) continue;
            if(visited[nextX][nextY]) continue;
            
            visited[nextX][nextY] = true;
            q.offer(new Location(nextX, nextY));
        }
        
    }
  }

 

그래서 큐에서 새로운 위치를 뽑아내면, 그 위치에서 킬 수 있는 불을 전부 켜면된다.

단, 이미 켜져있는 경우는 카운팅 안하기 때문에 생략한다.

 

public static void BFS(){
    Queue<Location> q = new LinkedList<>();
    q.offer(new Location(1,1));

    while(!q.isEmpty()){
        Location newLoc = q.poll();

        for(int i=0;i<map[newLoc.x][newLoc.y].size();i++){
            Location next = map[newLoc.x][newLoc.y].get(i);

            if(onoff[next.x][next.y]) continue;

            onoff[next.x][next.y] = true;
            result++;
        }

        for(int d=0;d<4;d++){
            int nextX = newLoc.x + drc[d][0];
            int nextY = newLoc.y + drc[d][1];

            if(nextX<0 || nextX>=N+1 || nextY<0 || nextY>=N+1) continue;
            if(visited[nextX][nextY]) continue;
            if(!onoff[nextX][nextY]) continue; //불이 켜져있지 않으면 안됨 (여기)
            
            visited[nextX][nextY] = true;
            q.offer(new Location(nextX, nextY));
        }
        
    }
  }

 

또한 불이 켜져있지 않으면 이동할 수 없기 때문에 큐에 추가할 때 체크해야 한다.

 

 

 

또한 2) 이미 지나온 길인데 뒤늦게 불이 들어왔다면?에 대한 대처가 필요하다. (중요 포인트!)

 

 

 

예를 들어 다음과 같은 문제가 있다고 하자. 각 칸에는 불을 켤 수 있는 위치가 적혀있는 것이다.

(1,1) ~ (1,5)까지는 무리없이 방을 카운팅할 수 있다.

 

 

근데 만약 (1,1)에서 상/하/좌/우 순으로 탐색 후 우로 계속 직진하고 있는 것이라면 (1,5)에서 켠 (2,1)로는 어떻게 갈 것인가?

그래서 한 번도 불을 켜지 않은 방에 불이 켜졌다면 다시 (1,1)을 큐에 넣어주고 visited를 초기화시켜 다시 탐색해주는 과정이 필요하다.

 

public static void BFS(){
    Queue<Location> q = new LinkedList<>();
    q.offer(new Location(1,1));

    while(!q.isEmpty()){
        Location newLoc = q.poll();

	//여기! visited 초기화
        if(newLoc.x==1 && newLoc.y==1) {
            visited = new boolean[N+1][N+1];
            visited[1][1] = true;
        }

        for(int i=0;i<map[newLoc.x][newLoc.y].size();i++){
            Location next = map[newLoc.x][newLoc.y].get(i);

            if(onoff[next.x][next.y]) continue;

            onoff[next.x][next.y] = true;
            result++;

            //여기! 새로운 불이 켜졌다! (1,1) 다시 추가
            if(newLoc.x!=1 || newLoc.y!=1) q.offer(new Location(1,1));
        }

        for(int d=0;d<4;d++){
            int nextX = newLoc.x + drc[d][0];
            int nextY = newLoc.y + drc[d][1];

            if(nextX<0 || nextX>=N+1 || nextY<0 || nextY>=N+1) continue;
            if(visited[nextX][nextY]) continue;
            if(!onoff[nextX][nextY]) continue;
            
            visited[nextX][nextY] = true;
            q.offer(new Location(nextX, nextY));
        }
        
    }
  }

 

 

 

---

3. 전체 코드

---

 

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

class Main {

    static int N;
    static List<Location>[][] map;
    static Queue<Location> onList = new LinkedList<>(); //불 켜진 곳만 있음
    static boolean[][] onoff; //이미 켜진 불인지 확인용
    static boolean[][] visited; //DFS 방문 체크용
    static int[][] drc = {{-1,0},{1,0},{0,-1},{0,1}};
    
    static int result = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String NM = br.readLine();
        StringTokenizer st = new StringTokenizer(NM, " ");
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        map = new ArrayList[N+1][N+1];
        for(int i=0;i<N+1;i++){
            for(int j=0;j<N+1;j++){
                map[i][j] = new ArrayList<>();
            }
        }

        onoff = new boolean[N+1][N+1]; // 1부터 시작
        onoff[1][1] = true;//언제나 (1,1)은 시작점
        
        for(int i=0;i<M;i++){
            String xyab = br.readLine();
            st = new StringTokenizer(xyab," ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            map[x][y].add(new Location(a,b));
        }

        BFS();
        
        System.out.println(result+1);//이미 켜져있는 (1,1) 포함
        br.close();
    }

    public static void BFS(){
        Queue<Location> q = new LinkedList<>();//갈 수 있는 경로
        q.offer(new Location(1,1));

        while(!q.isEmpty()){
            Location newLoc = q.poll();

            if(newLoc.x==1 && newLoc.y==1) {
                visited = new boolean[N+1][N+1];
                visited[1][1] = true;
            }

            //불켜기
            for(int i=0;i<map[newLoc.x][newLoc.y].size();i++){
                Location next = map[newLoc.x][newLoc.y].get(i);

                if(onoff[next.x][next.y]) continue; //이미 켜져있는 건 패스

                onoff[next.x][next.y] = true;
                result++;

                if(newLoc.x!=1 || newLoc.y!=1) q.offer(new Location(1,1));
            }

            //다음으로 이동(큐에 넣기)
            for(int d=0;d<4;d++){
                int nextX = newLoc.x + drc[d][0];
                int nextY = newLoc.y + drc[d][1];

                if(nextX<0 || nextX>=N+1 || nextY<0 || nextY>=N+1) continue; //경계체크
                if(visited[nextX][nextY]) continue;
                if(!onoff[nextX][nextY]) continue; //불이 켜져있지 않으면 안됨
                
                visited[nextX][nextY] = true;
                q.offer(new Location(nextX, nextY));
            }
            
        }
        
    }

    public static class Location{
        int x;
        int y;
        public Location(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}