BOJ_11967_불켜기 (Java)

[Gold II] 불켜기 - 11967

문제 링크

성능 요약

메모리: 26468 KB, 시간: 248 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 9월 21일 10:11:57

문제 설명

농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.

베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다.

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

입력

첫 번째 줄에는 N(2 ≤ N ≤ 100)과, M(1 ≤ M ≤ 20,000)이 정수로 주어진다.

다음 M줄에는 네 개의 정수 x, y, a, b가 주어진다. (x, y)방에서 (a, b)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다.

출력

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

문제 풀이

Area 클래스: (r,c) 좌표를 나타내는 클래스로, HashMap에서 키로 사용하기 위해 hashCode와 equals 메서드를 오버라이드합니다.

각 방의 상태를 3가지로 나누어 저장 (LIGHT_ON, VISITED, CAN_VISIT).

(1, 1) 부터 BFS 현재 위치의 스위치로 켤 수 있는 모든 불을 켭니다. 상하좌우로 이동할 수 있는지 확인합니다. 이동할 수 있으면 큐에 추가하고 상태를 업데이트합니다.

코드

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

public class Main {
    static int[] dr = { 0, 0, 1, -1 };
    static int[] dc = { 1, -1, 0, 0 };
    private static final int LIGHT_ON = 1;
    private static final int VISITED = 2;
    private static final int CAN_VISIT = 3;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Map<Area, List<Area>> map = new HashMap<>();

        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            Area cur = new Area(x, y);
            map.computeIfAbsent(cur, k -> new ArrayList<>()).add(new Area(a, b));
        }

        int result = bfs(n, map);
        System.out.println(result);

        br.close();
    }

    private int bfs(int n, Map<Area, List<Area>> map) {
        Queue<Area> queue = new ArrayDeque<>();
        int[][] board = new int[n+1][n+1];
        board[1][1] = VISITED;
        queue.add(new Area(1, 1));
        int cnt = 1;

        while (!queue.isEmpty()) {
            Area current = queue.poll();
            if (map.containsKey(current)) {
                for (Area light : map.get(current)) {
                    if (board[light.r][light.c] == VISITED || board[light.r][light.c] == LIGHT_ON) continue;
                    cnt++;
                    if (board[light.r][light.c] == CAN_VISIT) {
                        queue.add(light);
                        board[light.r][light.c] = VISITED;
                    } else {
                        board[light.r][light.c] = LIGHT_ON;
                    }
                }
            }

            for (int d = 0; d < 4; d++) {
                int nr = current.r + dr[d];
                int nc = current.c + dc[d];
                if (nr < 1 || nr > n || nc < 1 || nc > n || board[nr][nc] == VISITED || board[nr][nc] == CAN_VISIT) continue;

                if (board[nr][nc] == LIGHT_ON) {
                    board[nr][nc] = VISITED;
                    queue.add(new Area(nr, nc));
                    continue;
                }

                board[nr][nc] = CAN_VISIT;
            }
        }
        return cnt;
    }
}

class Area {
    int r, c;

    public Area(int r, int c) {
        this.r = r;
        this.c = c;
    }

    @Override
    public int hashCode() {
        return c * 20000 + r;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Area a = (Area) o;
        return this.r == a.r && this.c == a.c;
    }
}