Jin의 일상

문제 설명

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) 방의 불을 켜고 끌 수 있다는 의미입니다.

한 방에 여러 개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있습니다. 

아래 링크에서 15개의 샘플 케이스를 다운로드 받을 수 있습니다.

www.usaco.org/current/data/lightson_silver_dec15.zip

알고리즘

1. 각 방에는 여러 개의 스위치가 있습니다. 따라서 매트릭스를 만들어서 다른 방의 스위치 좌표들을 저장합니다

위 입력을 토대로 한 예시 매트릭스입니다. 이 매트릭스는 switchs라고 부르겠습니다.

2. 스위치의 상태(on/off)와 베스가 이동 가능한 방인지를 표현할 매트릭스를 만듭니다.

이 매트릭스는 board라고 부르겠습니다.

불이 꺼진 상태 : 0

불이 켜진 상태 : 1

베스가 이동 가능한 방 : 2

베스는 항상 (1, 1)에서 출발한다고 했으므로, (1, 1)의 초기값은 2입니다.

3. 베스의 출발 지점인 (1, 1)을 queue 리스트에 담습니다.

  - queue 리스트에 들어 있는 좌표는 다른 방의 스위치를 탐색하기 위해 사용됩니다.

  - queue에 리스트에 값이 없어질 때 까지 4 ~ 4-2-1 과정에 대한 반복문이 수행됩니다.

4. queue에 있는 좌표 (1, 1)을 빼내고, 해당 좌표의 switchs 매트릭스에 있는 모든 다른 방의 스위치를 누릅니다.

  - 스위치를 켠 방의 상하좌우를 탐색하여 주변에 2가 있는지 확인합니다.

4-1. 주변에 2가 없다면 board 매트릭스의 해당 좌표에 1을 입력합니다.

  (불만 켭니다 : 해당 방에는 베스가 들어갈 수 없습니다.)

4-2. 주변에 2가 있다면 board 매트릭스의 해당 좌표에 2를 입력합니다.

 (불이 켜져 있는 인접한 방이므로, 베스가 들어갈 수 있습니다.)

  - 주변에 1이 남아 있는 경우를 고려하여, 다시 한 번 상하좌우를 탐색해야 합니다

4-2-1. 상하좌우로 인접한 방에 1이 있는지 확인한 후, 존재한다면 2로 수정합니다. 

 -  4-2-1번 작업은 BFS 알고리즘이 재귀적으로 수행되어야 합니다.

 -  2로 수정된 방의 좌표에서는 switchs에 기록된 정보들의 탐색이 이뤄지지 않았으므로, queue에 담습니다.

* 4-2-1 작업이 재귀적으로 수행되어야 하는 이유

첫 번째 그림은, 기존에 불 켜져있는 방들이 밀집됐지만, 베스가 들어갈 수 없는 방을 표현했습니다.

두 번째 그림에서 (1, 2)에 불이 켜짐으로써 나머지 (2, 2), (3, 2), (3, 3)도 들어갈 수 있는 방으로 변해야 하는 상황이 되었습니다. 따라서 4-2-1 작업은 재귀적으로 수행되어야 합니다. 그 결과는 세 번째 그림과 같습니다.

코드

import sys
from collections import deque
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

n, m = map(int, input().split())  # n : n x n의 방을 만듦, m : m개의 데이터를 받음
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

board = [[0] * (n+1) for _ in range(n+1)]  # 1: 불 켜짐, 2: 이동 가능
board[1][1] = 2
switchs = [[[] for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    x, y, a, b = map(int, input().split())
    switchs[x][y].append([a, b])


def BFS(x, y):
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0 < xx <= n and 0 < yy <= n:
            if board[xx][yy] == 1:
                board[xx][yy] = 2
                queue.append([xx, yy])
                BFS(xx, yy)


cnt = 1
queue = deque([[1, 1]])
while queue:
    x, y = queue.popleft()
    for a, b in switchs[x][y]:
        for i in range(4):
            aa = a + dx[i]
            bb = b + dy[i]
            if 0 < aa <= n and 0 < bb <= n:
                if board[a][b] == 2:
                    break

                if board[aa][bb] == 2:
                    cnt += 1
                    board[a][b] = 2
                    queue.append([a, b])
                    BFS(a, b)
                    break
        if board[a][b] == 0:
            board[a][b] = 1
            cnt += 1
print(cnt)