[파이썬] 백준 11976 : 불켜기 (골드2)

[파이썬] 백준 11976 : 불켜기 (골드2)

• https://www.acmicpc.net/problem/11976

---

풀이

방향성 생각

• 시작점에서 BFS 돌리기.
• 불을 킬 수 있으면 해당 (x,y)와 연결된 노드 (xx,yy)로 불을 켜주기.
• (x,y)의 인접노드 (nx,ny)에서 첫방문 + 접근 가능한 경우 큐에 추가하기.
• 불 켜진 노드 (xx,yy) 기준에서 인접노드를 탐색하고, 새로 불 켜진 노드 (xx,yy) 주변 노드가 하나라도 V가 true인 경우 (xx,yy)를 큐에 넣으면 된다.
• 주의점은 table[(x,y)]에서 전부 훑지 말고, 업데이트 되는 노드만 방문하도록 수정하기.
• 정답은 갈 수 있는 곳이 아니라, 불을 켤 수 있는 곳이다. V 배열의 element 합이 아니라, access 배열 element의 합이다.

 

---

전체코드

from collections import deque, defaultdict as dd
import sys

input = lambda : sys.stdin.readline().strip()
inside = lambda x,y : 0<=x<N and 0<=y<N
dires = [(1,0),(0,1),(-1,0),(0,-1)]

N,M = map(int,input().split())
table = dd(list)
for _ in range(M):
    cx,cy,nx,ny = map(lambda x : int(x)-1, input().split())
    table[(cx,cy)].append((nx,ny))

V = [[False]*N for _ in range(N)]
V[0][0] = True

access = [[False]*N for _ in range(N)]
access[0][0] = True

Q = deque([(0,0)])
while Q:
    x,y = Q.popleft()

    # 1. 새로 불을 켜는 방 처리
    temp = []
    for xx,yy in table[(x,y)]:
        if not access[yy][xx]:
            access[yy][xx] = True
            temp.append((xx,yy))

    # 2. 인접 노드 탐색
    for dx,dy in dires:
        nx,ny = x+dx,y+dy
        if inside(nx,ny) and not V[ny][nx] and access[ny][nx]:
            V[ny][nx] = True
            Q.append((nx,ny))

    # 3. 새로 불 켜진 곳 주변에 방문한 곳이 있는지 확인
    for xx,yy in temp:
        for dx,dy in dires:
            nx,ny = xx+dx,yy+dy
            if inside(nx,ny) and V[ny][nx]:
                if not V[yy][xx]:
                    V[yy][xx] = True
                    Q.append((xx,yy))
                break

# 4. 불이 켜진 방의 개수 계산
answer = sum(sum(row) for row in access)
print(answer)

---

코멘트

.