[BOJ/python]1261번 알고스팟

백준 1261번 알고스팟 파이썬, BFS, 다익스트라

문제 링크 - https://www.acmicpc.net/problem/1261

1261번: 알고스팟

다익스트라 문제 분류에서 찾은 문제였다. 아무리 봐도 BFS로 간단하게 풀 수 있을 것 같아서 그렇게 풀었다. 벽 부수고 이동하기 문제랑 거의 유사하다.

1-1. 풀이

• 현재 노드에 방문하기 위해서 부숴야하는 벽의 개수를 방문 표시에 저장하며 BFS를 실행한다.
• 방문하지 않은 경우나 이미 방문했지만 현재 부숴야 하는 벽의 개수가 더 적은 경우일 때 방문 표시를 갱신한다.
• 방문하는 곳이 벽인지 아닌지에 따라 개수를 현재까지 부순 벽에 +1을 할지 안할지 결정한다.

1-2. 코드

from collections import deque

M,N = map(int,input().split())
G=[[0 for _ in range(M)]for _ in range(N)]
for i in range(N):
    l = input()
    for j in range(M):
        G[i][j]=int(l[j])

visited = [ [-1 for _ in range(M)] for _ in range(N) ]
def BFS():
    q = deque([[0,0,0]])
    visited[0][0]=0
    while q :
        x,y, cost = q.popleft()
        for nx,ny in ([x+1,y],[x-1,y],[x,y+1],[x,y-1]):
            if 0<=nx<N and 0<=ny<M:
                if G[nx][ny] == 0 :
                    if visited[nx][ny]>cost or visited[nx][ny]==-1:
                        visited[nx][ny]=cost
                        q.append([nx,ny,visited[nx][ny]])

                else:
                    if visited[nx][ny]>cost+1 or visited[nx][ny]==-1:
                        visited[nx][ny]=cost+1
                        q.append([nx,ny,visited[nx][ny]])
BFS()
print(visited[N-1][M-1])

2-1. 다익스트라 응용 풀이

위에서는 visited 배열에 현재 벽을 부순 개수가 더 적다면 갱신해주는 식으로 BFS를 이용했다.

하지만 queue가 아닌 heap을 사용해서 처음부터 벽을 적게 부수고 방문할 수 있는 노드를 먼저 방문할 수 있다.

즉 가장 벽을 적게 부순 경우가 heap에서 먼저 pop되고 이후에 벽을 많이 부순 경우가 pop되므로 heap에 남은 것들이 있더라도 목적지에 도착하면 BFS를 종료해야 한다.

2-2. 다익스트라 응용 코드

from heapq import heappop, heappush
M,N = map(int,input().split())
G=[[0 for _ in range(M)]for _ in range(N)]
for i in range(N):
    l = input()
    for j in range(M):
        G[i][j]=int(l[j])

visited = [ [-1 for _ in range(M)] for _ in range(N) ]
def BFS():
    q = []
    heappush(q, [0,0,0])
    visited[0][0]=1
    
    while q :
        cost, x,y = heappop(q)
        if x==N-1 and y==M-1:
            print(cost)
            break
        for nx,ny in ([x+1,y],[x-1,y],[x,y+1],[x,y-1]):
            if 0<=nx<N and 0<=ny<M:
                if visited[nx][ny]==-1:
                    if G[nx][ny]==1:
                        visited[nx][ny]=cost+1
                        heappush(q, [cost+1, nx,ny])
                    else:
                        visited[nx][ny]=cost
                        heappush(q, [cost, nx, ny])

BFS()