[python] 백준 11967 불켜기

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

11967번: 불켜기

 

문제 해결

• BFS로 방을 움직이면서 불을 켜는 문제
• 첫 번째 문제는 A방에서 B방의 불을 켤 수 있다는 것이다.(이는 문제에서 주어진다.)
  • 그러면 이동하면서 A방에서 킬 수 있는 불은 모두 켜야한다.
    • ( (i,j)위치의 방에 불이 켜지면 값이 0→1로 바뀌는 것으로 구현) 
• 두 번째 문제는 조건부로 동,서,남,북 중 방에 불이 켜져있는 방향으로만 움직일 수 있다는 것이다. 
  • 그런데 아직 불이 안켜져서 이동을 못하는데 미래에 다른 방을 통해 불을 켜서 이동할 수 있는 경우도 생길 수 있다.
  • 따라서 아직 방문을 안했고 불이 꺼져있어서 못들어가는 것이면 memo에 방위치 (i,j)를 넣은 다음 미래에 혹시 (i,j)불을 켰으면 그 때 이동할 수 있도록 한다.

 

CODE

from collections import deque

dxs = [-1, 1, 0, 0]
dys= [0, 0, -1, 1]
n, m = map(int, input().split())
graph = [[[] for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    a, b, c, d = map(int, input().split())
    graph[a][b].append((c,d))
answer = 0
visited = [[0]*(n+1) for _ in range(n+1)]
light = [[0]*(n+1) for _ in range(n+1)]
que = deque()
que.append((1,1))
visited[1][1] = 1
light[1][1] = 1
answer += 1
memo = [] # 아직 불이 안켜졌지만 미래에 커져 이동할 수 있는 곳

while que:
    x, y = que.popleft()
    for nx,ny in graph[x][y]:
        if light[nx][ny] ==0:
            light[nx][ny] = 1
            answer += 1
            if (nx,ny) in memo:
                visited[nx][ny] = 1
                memo.remove((nx,ny))
                que.append((nx,ny))
    for dx, dy in zip(dxs,dys):
        nx = x + dx
        ny = y + dy
        if 1<=nx<=n and 1<=ny<=n:
            if visited[nx][ny] ==0 and light[nx][ny]==1:
                visited[nx][ny] = 1
                que.append((nx,ny))
            elif visited[nx][ny] ==0 and light[nx][ny]==0:
                memo.append((nx,ny))

print(answer)