[JAVA] 백준 11967번: 불켜기

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

11967번: 불켜기

✅ 골드 Ⅱ

 

🔶 풀이

베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오.

(1, 1) 부터 상, 하, 좌, 우로 움직일 수 있고 불이 켜져 있는 곳만 이동할 수 있다.

 

출력에서 조심해야 할 건 베시가 이동할 수 있는 방의 개수가 아니라 불을 켤 수 있는 방의 최대 개수다.

질문 게시판 보니까 실수하시는 분들이 정말 많았다.

 

상하좌우로 이동하는 문제는 보통 bfs로 풀면 된다.

이 문제도 동일하게 bfs가 기본 베이스이고, 불을 키고 끄는 것만 신경써주면 된다.

 

bfs 조건:

1️⃣ 불이 켜져 있는 곳만 이동할 수 있다.

2️⃣ 맵의 범위를 벗어나거나 방문한 곳은 방문할 필요가 없다.

 

두 가지만 신경써주면 된다.

그리고 flag 변수를 만들어서 불을 켰을 경우, 베시가 이동할 수 있는 방이 생기기 때문에 bfs를 한 번 더 돌려주면 된다.

 

 

<최종 코드>

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

public class Main {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int cnt = 1;
    static int N;
    static boolean flag = false;
    static ArrayList<Node>[][] arrList;
    static boolean[][] map;
	
    public static class Node {
        int x, y;
		
        public Node (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
	
    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());
        int M = Integer.parseInt(st.nextToken());
		
        arrList = new ArrayList[N+1][N+1];
		
        for (int i=1; i<=N; i++) {
            for (int j=1; j<=N; j++) {
                arrList[i][j] = new ArrayList<>();
            }
        }
		
        map = new boolean[N+1][N+1];
        map[1][1] = true;
		
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
			
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
			
            arrList[a][b].add(new Node(c, d));
        }
		
        bfs();
        System.out.println(cnt);
    }
	
    public static void bfs() {
        Queue<Node> q = new LinkedList<>();
        boolean[][] visited = new boolean[N+1][N+1];
		
        q.add(new Node(1, 1));
        flag = false; // 초기화 변수
		
        while (!q.isEmpty()) {
            Node now = q.poll();
			
            for (int d=0; d<4; d++) {
                int nx = now.x + dx[d];
                int ny = now.y + dy[d];
				
                if (nx < 1 || ny < 1 || nx > N || ny > N) continue;
                if (!map[nx][ny] || visited[nx][ny]) continue;
				
                q.add(new Node(nx, ny));
                visited[nx][ny] = true;
            }
			
            // 도착한 방에서 불을 켤 수 있는 경우
            for (Node node : arrList[now.x][now.y]) {
                if (!map[node.x][node.y]) {
                    flag = true; // 불을 켰을 경우 베시가 이동할 수 있는 방이 새로 생김
                    map[node.x][node.y] = true;
                    cnt++;
                }
            }
        }
		
        // 베시가 이동할 수 있는 방이 새로 생겼기 때문에 bfs 재호출
        if (flag) {
            bfs();
        }
    }
}