-
[BOJ/python]1261번 알고스팟알고리즘/BOJ 2022. 7. 6. 22:50
백준 1261번 알고스팟 파이썬, BFS, 다익스트라
문제 링크 - https://www.acmicpc.net/problem/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()
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ/python]10282번 해킹 (0) 2022.07.06 [BOJ/python]1162번 도로포장 (0) 2022.07.06 [BOJ/python]11375번 열혈강호 (0) 2022.07.06 [BOJ/python]2213번 트리의 독립집합 (0) 2022.07.06 [BOJ/python]2208번 보석줍기 (0) 2022.07.06