https://www.acmicpc.net/problem/1261
1261번: 알고스팟첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미www.acmicpc.net
이래서 사람들이 비싼돈내고 알고리즘강의를 듣는구나 싶다.
‘가중치가 있는 경로찾기’ 이다.
벽을 지나갈때는 1의 가중치가, 아니면 가중치가 없다고 생각한다. 풀이는 bfs와 거의 같다.
다른점은, 최대한 벽을 부수지 않아야되므로,
1의 가중치가 있는점을 탐색하기 전에, 가중치가 없는 모든 노드를 탐색해야만 한다.
내머리로는 도저희 몰라서 힌트를 얻었다.
바로, 가중치가 0일때는 appendleft()를 해서 큐의 앞에 넣고, 1일때는 append()로 뒤에 넣는다.
이러면, 어떻게던 가중치가 0인 노드들부터 탐색하게 된다. 이후에도 이를 반복하며 목표에 도달하면, 이는 가중치가 가장 적은 상태에서 목표에 도착하는 것이다.
que자체에 부순 벽 갯수를 넣은 풀이
import sysfrom collections import dequeinput=sys.stdin.readline
moves=[(-1,0),(1,0),(0,-1),(0,1)]def bfs(start_i=0,start_j=0): que=deque()
que.append((start_i,start_j,0)) while que: i,j,wall=que.popleft()
for a,b in moves: tmp_i,tmp_j=i+a,j+b
if 0<=tmp_i<m and 0<=tmp_j<n and graph[tmp_i][tmp_j]!=-1:
if tmp_i==m-1 and tmp_j==n-1:
graph[tmp_i][tmp_j]=-1
print(wall) exit()
elif graph[tmp_i][tmp_j]=='0':
graph[tmp_i][tmp_j]=-1
que.appendleft((tmp_i,tmp_j,wall))
elif graph[tmp_i][tmp_j]=='1':
graph[tmp_i][tmp_j]=-1
que.append((tmp_i,tmp_j,wall+1))
n,m=map(int,input().split())if n==m==1: print(0) exit()
graph=[list(input().strip()) for _ in range(m)]bfs()dist[i][j]에 “[i][j]까지 도달하기에 최소한으로 부순 벽의 수” 를 저장한 풀이
import sysfrom collections import dequeinput=sys.stdin.readline
moves=[(-1,0),(1,0),(0,-1),(0,1)]def bfs(start_i=0,start_j=0): que=deque()
que.append((start_i,start_j)) while que: i,j=que.popleft()
for a,b in moves: tmp_i,tmp_j=i+a,j+b
if 0<=tmp_i<m and 0<=tmp_j<n and graph[tmp_i][tmp_j]!=-1:
if tmp_i==m-1 and tmp_j==n-1:
dist[tmp_i][tmp_j]=dist[i][j] return
elif graph[tmp_i][tmp_j]=='0':
graph[tmp_i][tmp_j]=-1
dist[tmp_i][tmp_j]=dist[i][j]
que.appendleft((tmp_i,tmp_j))
elif graph[tmp_i][tmp_j]=='1':
graph[tmp_i][tmp_j]=-1
dist[tmp_i][tmp_j]=dist[i][j]+1
que.append((tmp_i,tmp_j)) n,m=map(int,input().split())
dist=[[0 for _ in range(n)]for _ in range(m)]
graph=[list(input().strip()) for _ in range(m)]bfs()print(dist[m-1][n-1])