백준 2665_미로만들기

미로만들기(백준 2665)

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

문제를 푸는 아이디어는
BFS를 통해 탐색하면서
목적지까지 ‘0’을 밟은 횟수를 세는 방식이였으며,
그에 따른 0을 밟은 횟수를 최소화한 값을 구하는 것!

다만, heapq(우선순위 큐)와 set() 을 사용하여
풀었으나, ‘시간 초과’가 났었고,
visit 배열과, deque 를 사용했을 때는 ‘메모리 초과’가 나버려
‘구현 방식’에 뭔가 놓친게 있다고 생각하였다

가~장 중요했던 점은
‘방문’ 시점을 표기하는 것이였다
(자료구조의 변화는 상관이 없었다…)

closePos.add()를 for문 밖에 두었을때는
while이 한번 돌때,
한번만 들어가며, 이에 따라서 ‘같은 노드’가
우선순위 큐에 들어갈 가능성이 있으며,
이에 따라서 ‘우선순위 큐’의 ‘삽입’이 호출되는 수가 늘어난다고 생각하였다

그러므로 for()문에 ‘새로운’노드를 방문할 경우에
closePos.add()를 호출하여,
새로운 노드는 이미 ‘방문’하였다고 미리 도장을 찍어두는 방식으로 통과하였다

Code

import sys
import heapq

# BFS
# 이미 주어진 그래프에서
# 0,0 -> (n -1, n-1)로 갈때
# 만나는 0의 최소 개수 구하기
# (미로를 고치려고 생각하지 말고)
# 코드를 짤 때 고려해야 할점
# 그냥 노드에 여기까지 오면서 
# 밟은 0의 개수를 적는 방식이 좋을듯??
# 더 작은 값으로 바꿔주기

inp = sys.stdin.readline

nNum = int(inp().strip())
graph = []
for i in range(nNum):
    graph.append(list(map(int, inp().strip())))

def bfs(graph):
    minheap = []
    heapq.heappush(minheap,[0,0,0]) # cost, pos x , pos y

    closePos = set()

    while minheap:
        cost, posX, posY = heapq.heappop(minheap)

        if posX == nNum - 1 and posY == nNum - 1:
            print(cost)
            return

        # 여기다 넣으면 시간초과
        # closePos.add((posX,posY))

        for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
            newX = posX + dx
            newY = posY + dy

            if 0 <= newX < nNum and 0 <= newY < nNum and (newX,newY) not in closePos:
                closePos.add((newX,newY)) # 여기다 넣으면 통과
                if graph[newX][newY] == 0:
                    newCost = 1
                else:
                    newCost = 0
                
                heapq.heappush(minheap,[cost + newCost,newX,newY])

bfs(graph)