[Python 3] BOJ 11967 불켜기

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

 

 

시작점인 (1,1)부터, "불이 켜져 있는"방들을 걸어다녀야 한다.

각 방들을 움직이면서 다른 방의 불을 켤 수 있는 스위치들을 누르면서, 갈 수 있는 방들을 넓히는 것이 주요 포인트이다.

 

해당 문제가 일반적인 BFS문제랑 다른 이유는, 기존 bfs에서는 '내가 한 번 갈 수 없다고 판단한 장소는 다시 신경쓰지 않아도 된다.' 하지만, 여기 문제에서는 특정 방을 도착하면서 기존에 가지 못했던 방의 불이 켜지면서, 이제 갈 수 있는 방이 될 수도 있기 때문에, 방금 스위치를 켠 방이 기존에 내가 갔던 길로 연결되어 있는 방인지 확인해주는 과정을 통해 해결해야 한다. 

from collections import deque
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
data=list(list(list() for _ in range(n+1)) for _ in range(n+1))
visited=[list(0 for _ in range(n+1)) for _ in range(n+1)]
light=list(list(0 for _ in range(n+1)) for _ in range(n+1))
light[1][1]=1
for _ in range(m):
    x,y,a,b=map(int,input().split())
    data[x][y].append([a,b])
dx=[-1,0,0,1]
dy=[0,-1,1,0]
q=deque()
q.append([1,1])
while q:
    x,y=q.popleft()
    for i,j in data[x][y]:
        light[i][j]=1
        if visited[i][j]:
            continue
        for k in range(4):
            nx=i+dx[k]
            ny=j+dy[k]
            if 0<nx<=n and 0<ny<=n and light[nx][ny] and visited[nx][ny]:
                q.append([i,j])
                visited[i][j]=1
                break
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<nx<=n and 0<ny<=n and not visited[nx][ny]:
            if light[nx][ny]:
                q.append([nx,ny])
                visited[nx][ny]=1
answer=sum(light[i].count(1) for i in range(n+1))
print(answer)

data는 light switch들의 정보를 가지고 있는 list이다. 

visited는 불을 켠 방들을 다시 방문하지 않도록 방문했던 불 켜진 방들의 기록을 담고 있다.

여기서 중요한 포인트는, 불이 켜져 있지 않아서 가지 못했던 방들을 'visited'에 넣으면 안된다. 앞서 말했던 것 처럼, 기존 다른 스위치가 켜지면서 갈 수 있는 상황으로 바뀔 수도 있기 때문이다.

 light는 현재 방들의 상태가 불이 켜져 있는지, 꺼져 있는지 확인하는 list이다.

 

for i,j in data[x][y]:
        light[i][j]=1
        if visited[i][j]:
            continue
        for k in range(4):
            nx=i+dx[k]
            ny=j+dy[k]
            if 0<nx<=n and 0<ny<=n and light[nx][ny] and visited[nx][ny]:
                q.append([i,j])
                visited[i][j]=1
                break

 

해당 부분의 코드에서 스위치로 다른 방들의 불을 켠다.

이미 방문을 했던 불이 켜져 있는 방이면, 무시한다.

만약 방금 불을 켰는데, 옆에 있던 방이 불이 켜져있는 방문했던 방이면 다음 방문 리스트에 포함시킨다.