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

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

코드

import sys
from collections import deque, defaultdict
input = sys.stdin.readline

n, m = map(int, input().split())
switchs = defaultdict(list)
for _ in range(m):
    x, y, a, b = map(int, input().split())
    switchs[(x, y)].append((a, b))


dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

q = deque([(1, 1)])
# 불이 켜진 방 체크
lights = [[False]*(n+1) for _ in range(n+1)]
lights[1][1] = True
# 방문 여부 체크
visited = [[False]*(n+1) for _ in range(n+1)]
visited[1][1] = True

while q:
    x, y = q.popleft()
    # 현재 방의 스위치로 다른 방 불 켜기
    for a, b in switchs[(x, y)]:
        if lights[a][b]:
            continue
        lights[a][b] = True
        # 지금 불을 켠 (a, b)가 방문이 가능한 곳인지 확인. 가능하다면 큐에 넣기
        for j in range(4):
            na = a+dx[j]
            nb = b+dy[j]
            if 0 < na <= n and 0 < nb <= n and visited[na][nb]:
                q.append((a, b))
                visited[a][b] = True
                break

    # 인접한 방으로 이동
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0 < nx <= n and 0 < ny <= n and lights[nx][ny] and not visited[nx][ny]:
            q.append((nx, ny))
            visited[nx][ny] = True


result = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        if lights[i][j]:
            result += 1

print(result)

 

BFS를 수행하는데, 이동한 방에 있는 스위치로 불을 켜는 과정이 추가된 것 뿐이다. 이를 위해 방문 여부를 체크하는 `visited` 배열 외에도 불이 켜졌는지 체크하기 위한 `lights` 배열이 존재한다.

 

BFS는 다음과 같은 과정으로 수행된다.

1. 큐에서 첫번째 원소를 뽑는다.

2. 뽑은 첫번째 원소를 현재 방이라고 할 때, 현재 방의 스위치로 켤 수 있는 다른 방의 불들을 켠다. 이때 불을 켠 방의 상하좌우에 이미 방문 처리된 방이 있다면 그 방도 방문이 가능하므로 큐에 넣고 방문 처리한다.

3. 상하좌우를 탐색하여 이동 가능한 방을 큐에 넣고 방문 처리한다.

 

이렇게 새로 불을 켠 방을 처리할 때, 거기까지 다시 탐색하지 않고 방문 가능 여부만 탐색한 뒤에 큐에 넣으면 불필요한 연산을 줄일 수 있다.