[백준 11967번] 파이썬 - 불 켜기

백준 11967 - 불켜기

시간 제한 2초, 메모리 제한 512MB

# 조건

• 농부 존은 최근에 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)방의 불을 켜고 끌 수 있다는 의미이다.
• 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다.

출력

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

# 접근 방법

• bfs를 사용하면 간단히 풀릴 것 같았지만 꽤 까다로운 문제였다.
• 우선 1, 1부터 N, N까지이므로 N * 2 씩해주어 행과 열을 양 옆으로 1칸씩 늘려준다.
• 현재는 못 가지만 나중에 불이 켜진 방이 연결되어 갈 수도 있으므로 방문 표시 배열과, 불이 켜져있는 배열 2개를 사용해준다.
• 처음에 불을 켜는 방과 켜지는 방을, defaultdict를 사용하여 {켜는 방 : [켜지는 방]} 으로 저장해준다.
• 1, 1에서부터 불을 켜주는데 불을 켜준 방을 기준으로 4방향에 방문한적이 있다면 q에 넣어주어 재검사 할 수 있도록 해준다.
• 또한, 불을 켠 방을 기준으로 처음 방문하였지만 불이 켜진 곳이라면, 재검사를 위하여 4방향에 불이 켜진 곳을 q에 넣어준다.
• 복잡해보였지만, 체크 리스트를 2개를 사용해주니 금방 풀 수 있었다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque, defaultdict  

def bfs():  
    visited[1][1] = True  
    light_on[1][1] = True  
    q = deque([(1, 1)])  
    while q:  
        si, sj = q.popleft()  
        # 불 켤 수 있는 곳 켜주기  
        for ni, nj in turn_on[(si, sj)]:  
            if not light_on[ni][nj]:  
                light_on[ni][nj] = True  
                # 새로 불 켠 곳 4방향 중 방문한 적이 있다면 재탐색 대상  
                for d in range(4):  
                    li, lj = ni+di[d], nj+ dj[d]  
                    if visited[li][lj]:  
                        q.append((li, lj))  

        # 불을 켠 방 기준으로 4방향에 불 켜진 곳이 있는데 방문한 적이 없다면 재탐색 대상  
        for d in range(4):  
            li, lj = si + di[d], sj + dj[d]  
            if not visited[li][lj] and light_on[li][lj]:  
                q.append((li, lj))  
                visited[li][lj] = True  

N, M = map(int, input().split())  
turn_on = defaultdict(list)  
visited = [[False] * (N*2) for _ in range(N*2)]  
light_on = [[False] * (N*2) for _ in range(N*2)]  
di, dj = [1, -1, 0, 0], [0, 0, 1, -1]  
for _ in range(M):  
    x, y, a, b = map(int, input().split())  
    turn_on[(x, y)].append((a, b))  

bfs()  
result = 0  
for i in light_on:  
    result += i.count(True)  

print(result)