[BOJ] 11967. 불켜기(🥇, BFS)

문제

풀이

BFS를 사용해서 탐색했다. 가능한 모든 방의 불을 다 킬 수 있어야 하기 때문. 탐색을 하면서 큐에 담아야 하는 값들은 다음과 같다

방에 불은 켜졌지만 ⭕️ 아직 방문은 하지 않은 곳 ❌
방에 불은 켜지지 않았지만 ❌ 방문은 한 곳 ⭕️

여기서 불이 켜졌다는 이 방의 불을 켤 수 있는 스위치가 있는 곳을 지나쳐왔다는 것이고, 방문을 했다는 것은 불이 켜진 방에서 이동할 수 있는 곳이었다는 것.

여기서 방에 불도 켜졌고 ⭕️ 방문도 한 곳은 ⭕️ 갈 필요가 없다.

# 불켜키
import sys
from collections import deque, defaultdict
input = sys.stdin.readline

n, m = map(int, input().rstrip().split())
room = defaultdict(list)
visited = defaultdict(bool)
light = dict()

for _ in range(m):
    x, y, a, b = map(lambda x: int(x)-1, input().rstrip().split())
    room[(x, y)].append([a, b])

queue = deque([(0, 0)])
light[(0, 0)] = True
visited[(0, 0)] = True
while queue:
    x, y = queue.popleft()

    for nx, ny in room[(x, y)]:
        # 아직 방에 불이 켜지지 않았지만 방문은 한 곳 
        if not light.get((nx, ny)):
            light[(nx, ny)] = True
            if visited[(nx, ny)]:
                queue.append((nx, ny))

    for nx, ny in (x-1, y), (x+1, y), (x, y-1), (x, y+1):
        if nx<0 or ny<0 or nx>=n or ny>=n:
            continue
		
        # 아직 방문은 하지 않았지만 불은 켜져있는 곳
        if not visited[(nx, ny)]:
            visited[(nx, ny)] = True
            if light.get((nx, ny)):
                queue.append((nx, ny))

print(light)
print(len(light))

"""
3 6
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 1
"""