[BOJ] 11967. 불 켜기(Python) / BFS

11967번: 불켜기

각 방에서 불을 켤 수 있는 곳의 위치가 주어지면 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다. 불을 켤 수 있는 방의 최대 개수를 구하는 문제이다.

• 사용 알고리즘 : BFS 너비 우선 탐색
• 근래 풀어본 BFS 문제 중에 내 기준 가장 까다로운 문제였다.. 처음에 쉬운 문제라고 생각했는데 하다보니 자꾸 꼬이고 잘 안 되어서 다른 분의 블로그를 참고했다. 코드를 깔끔히 잘 짜주셔서 많은 도움이 됐다!
• 참고한 블로그 링크는 아래에 첨부했다.
• 내가 불을 켠 곳이 현재는 내 위치에서 떨어져 있는 곳이지만 나중에 방들의 불을 켜며 연결될 수 있기 때문에 체크 맵을 하나만 사용하면 안 되었었다.
• 방문 표시만 하는 visited 배열과 불을 켰는지 여부를 표시하는 lights 배열을 따로 만들어 두 개의 맵을 각각 운영하는 것이 상당히 많은 생각을 요구했다.
• 큐에서 꺼낸 값에 대해 두 번의 검사가 필요하다.
  • 첫째, 딕셔너리에 저장한 정보를 참고해 현 위치에서 불 켤 수 있는 곳을 방문하며 불을 새로 켤 수 있는 곳을 켜고(result += 1), lights에 표시한다.
    • 새로 불을 켠 방의 상하좌우 4방향 연결된 곳을 탐색하며 방문한 적이 있다면, 재검사의 대상이 되므로 큐에 추가한다.
  • 둘째, 현재 위치에서 4방향 연결된 위치를 확인하며 첫 방문인데 이미 불이 켜진 곳이라면 재검사의 대상이 되므로 큐에 추가하고 visited에 방문 표시한다. 
• 큐에 담긴 값에 대한 모든 검사가 끝나면, 불을 켠 방의 갯수를 리턴한다.

 

- 참고한 블로그 주소 첨부 -

velog.io/@haruponea/%EB%B0%B1%EC%A4%80-11967-%EB%B6%88%EC%BC%9C%EA%B8%B0

 

파이썬 코드는 다음과 같다.

---

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

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

def bfs():
    result = 1      # 불 켤 수 있는 방의 갯수
    visited = [[0] * N for _ in range(N)]   # 방문 표시
    visited[0][0] = 1
    lights = [[0] * N for _ in range(N)]    # 불 켠 방 표시
    lights[0][0] = 1
    Q = deque([(0, 0)])
    while Q:
        r, c = Q.popleft()
        for tr, tc in turnInfo[(r, c)]:   # 불 켤 수 있는 곳(딕셔너리 참조)
            if not lights[tr][tc]:
                lights[tr][tc] = 1      # 새로 불 켜기
                result += 1
                for d in range(4):      # 4방향 연결된 곳
                    nr = tr + dr[d]
                    nc = tc + dc[d]
                    if not (0 <= nr < N and 0 <= nc < N):
                        continue
                    if visited[nr][nc]:     # 방문한 적 있으면(새로 연결되어 또 불을 켤 곳이 있을 수 있으므로)
                        Q.append((nr, nc))  # 큐에 담기
        
        # 현 위치를 기준으로
        for d in range(4):      # 4방향 연결된 곳
            nr = r + dr[d]
            nc = c + dc[d]
            if not (0 <= nr < N and 0 <= nc < N):
                continue
            # 첫 방문인데 이미 불 켜진 곳이면
            if not visited[nr][nc] and lights[nr][nc]:
                Q.append((nr, nc))      # 재검사를 위해 큐에 담기
                visited[nr][nc] = 1     # 방문 표시
                
    return result


# main
N, M = map(int, input().split())
turnInfo = defaultdict(list)	# 각 위치에서 불 켤 수 있는 위치 정보 저장
for _ in range(M):
    sr, sc, tr, tc = map(int, input().split())
    turnInfo[(sr-1, sc-1)].append((tr-1, tc-1))

print(bfs())

---

• 시간 : 204ms / 메모리 : 128832kb(PyPy3 제출)
• 고찰 :  배운 점이 많은 문제였다. 풀어보길 참 잘했다. BFS를 활용해 낼 수 있는 문제가 정말 많은 것 같다. 정말 경험의 싸움이다. 많이 풀고 보고 생각하고 코딩하자! 힘내자.