[백준 | Python] #11967 - 불켜기

11967번: 불켜기

문제

N*N개의 격자 구조의 방이 있고 각 방에는 다른 방의 불을 켤 수 있는 스위치가 있다. 불이 켜져 있으면서 현재 위치한 방에서 상하좌우로 인접한 방만 이동할 수 있다. 유일하게 불이 켜져 있는 방인 (1,1)의 방에서 출발할 때 불을 켤 수 있는 방의 수의 최댓값을 구하여라.

아이디어 및 구현

격자 모양에서 구조에서 인접한 방을 탐색하려면 당연히 BFS를 떠올리지 아니할 수 없다.

하지만 ‘불을 켜는 방식’으로 다른 방의 접근 조건을 변화시키는 문제는 생소하여 생각이 필요했다.

 

우선 검색량을 줄이기 위해 현재 접근 가능한 방을 기록해야 한다.

그러면서 ‘새롭게 접근 가능한 방’의 리스트도 꾸준히 업데이트 하도록 한다.

이러한 리스트를 기록하지 않으면 매번 접근 가능한 방을 모두 뒤지게 되므로 타임 아웃이 날 것이다.

 

그리고 새롭게 접근 가능한 방에서 켤 수 있는 불을 모두 켠 후 새롭게 불이 켜진 방들이 접근 가능한지 파악해야 한다.

이때 새롭게 불이 켜진 방들 주변에 불은 켜져 있지만 접근 불가능 하던 방이 있는지 확인해야 한다.

이러한 방들은 BFS로 탐색해주어 역시 새롭게 접근 가능한 방 리스트에 추가하도록 한다.

 

설명이 조금 난해하여 직접 코드를 보는 것이 더 쉬울 수 있겠다.

코드

from collections import deque

ITER = [(1,0),(0,1),(-1,0),(0,-1)] # 주변 방 탐색을 위한 iterator 역할의 변수

# 새롭게 불이 켜진 방이 접근 가능하다면
# 주변에 불이 켜져있지만 접근 불가능하던 방을
# bfs로 탐색하는 함수
def get_new_visitable(r,c):
    visitable[r][c] = 1
    new_visitable = [(r,c)]
    q = deque([(r,c)])

    while q:
        adj_r,adj_c = q.popleft()
        for dr,dc in ITER:
            x = adj_r + dr
            y = adj_c + dc
            if 0<x<=n and 0<y<=n and light[x][y] == 1 and visitable[x][y] == 0:
                visitable[x][y] = 1
                new_visitable.append((x,y))
                q.append((x,y))

    return new_visitable

# 입력
n,m = map(int, input().split())
switch = [[[] for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    x,y,a,b = map(int, input().split())
    switch[x][y].append((a,b))

light = [[0 for _ in range(n+1)] for _ in range(n+1)] # 불 켜진지 여부
light[1][1] = 1

visitable = [[0 for _ in range(n+1)] for _ in range(n+1)] # 현재 접근 가능 여부
visitable[1][1] = 1

new_visitable = deque([(1,1)])

# 새로이 방문할 수 있는 방이 있다면 반복
while new_visitable:
    _r,_c = new_visitable.popleft()

    # 새로이 방문한 방에서 켤 수 있는 불에 대해 반복
    for r,c in switch[_r][_c]:
        if light[r][c] == 1: continue
        light[r][c] = 1

        # 주변에 접근 가능한 방이 있다면
        # 방금 불을 켠 방과 주변에 접근 불가능하던 방을
        # new_visitable 큐에 추가
        for dr,dc in ITER:
            if 0<r+dr<=n and 0<c+dc<=n and visitable[r+dr][c+dc]:
                new_visitable += get_new_visitable(r,c)
                break

print(sum(sum(row) for row in light))

구현하다 보니 nested BFS(?)의 형태를 띄게 되었다. 독특한 문제인 것 같다.

알고리즘을 대놓고 알려줘도 제대로 풀기에 까다로운 문제로 생각된다. 좋은 문제인 듯.