백준 1261번 알고스팟

 

최단거리인데 가중치를 곁들인 최단경로...

다익스트라로 풀릴지도 모르겠으나 일단 bfs문제로 보고왔기에 bfs로 푼다.

 

nm까지 가는 1을 최소한으로 만나는 경로의 1의 횟수를 세야한다.

 

from collections import deque
import sys

m,n=map(int,sys.stdin.readline().rstrip().split())
str_graph=[]
for i in range(n):
    str_graph.append(sys.stdin.readline().rstrip())
graph=[[0]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        graph[i][j]=ord(str_graph[i][j])-ord('0')

q=deque()
q.append([0,0])
visited=[[-1]*m for _ in range(n)]
visited[0][0]=0
dr=[-1,0,1,0]
dc=[0,1,0,-1]
while q:
    cur_row,cur_col=q.popleft()
    cost=visited[cur_row][cur_col]
    for i in range(4):
        if cur_row+dr[i]>=n or cur_row+dr[i]<0 or cur_col+dc[i]>=m or cur_col+dc[i]<0:
            continue
        if visited[cur_row+dr[i]][cur_col+dc[i]]==-1 or visited[cur_row+dr[i]][cur_col+dc[i]]>cost+graph[cur_row+dr[i]][cur_col+dc[i]]:
            q.append([cur_row+dr[i],cur_col+dc[i]])
            visited[cur_row+dr[i]][cur_col+dc[i]]=cost+graph[cur_row+dr[i]][cur_col+dc[i]]
print(visited[n-1][m-1])

이렇게 작성했다.

근데 할때마다 느끼는건데 이건 정석으로 푸는건 아닌것같다

 

 

이것도 appendleft가 가능하다고 한다. 왜지 순서가 보장이 안될수도 있지않나?

이해했다 상태가 두개일때는 appendleft를 해도 문제가 되지않는다. 상태의 개수가 그 이상이면 문제될수있다.

그러므로 상태의 개수가 2개이상일때는 다익스트라를 써야한다.

일단 코드를 조금 수정해주자

from collections import deque
import sys

m,n=map(int,sys.stdin.readline().rstrip().split())
str_graph=[]
for i in range(n):
    str_graph.append(sys.stdin.readline().rstrip())
graph=[[0]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        graph[i][j]=ord(str_graph[i][j])-ord('0')

q=deque()
q.append([0,0])
visited=[[-1]*m for _ in range(n)]
visited[0][0]=0
dr=[-1,0,1,0]
dc=[0,1,0,-1]
is_end=False
while q:
    cur_row,cur_col=q.popleft()
    cost=visited[cur_row][cur_col]
    for i in range(4):
        if cur_row+dr[i]>=n or cur_row+dr[i]<0 or cur_col+dc[i]>=m or cur_col+dc[i]<0:
            continue
        if visited[cur_row+dr[i]][cur_col+dc[i]]==-1 or visited[cur_row+dr[i]][cur_col+dc[i]]>cost+graph[cur_row+dr[i]][cur_col+dc[i]]:
            if graph[cur_row+dr[i]][cur_col+dc[i]]==0:
                q.appendleft([cur_row+dr[i],cur_col+dc[i]])
            else:
                q.append([cur_row+dr[i],cur_col+dc[i]])
            visited[cur_row+dr[i]][cur_col+dc[i]]=cost+graph[cur_row+dr[i]][cur_col+dc[i]]
        if cur_row+dr[i]==n-1 and cur_col+dc[i]==m-1:
            print(cost+graph[cur_row+dr[i]][cur_col+dc[i]])
            is_end=True
            break
    if is_end:
        break

뭐지

 

from collections import deque
import sys

m,n=map(int,sys.stdin.readline().rstrip().split())
str_graph=[]
for i in range(n):
    str_graph.append(sys.stdin.readline().rstrip())
graph=[[0]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        graph[i][j]=ord(str_graph[i][j])-ord('0')

q=deque()
q.append([0,0])
visited=[[-1]*m for _ in range(n)]
visited[0][0]=0
dr=[-1,0,1,0]
dc=[0,1,0,-1]
is_end=False
if n==1 and m==1:
    print(0)
else:
    while q:
        cur_row,cur_col=q.popleft()
        cost=visited[cur_row][cur_col]
        for i in range(4):
            if cur_row+dr[i]>=n or cur_row+dr[i]<0 or cur_col+dc[i]>=m or cur_col+dc[i]<0:
                continue
            if visited[cur_row+dr[i]][cur_col+dc[i]]==-1 or visited[cur_row+dr[i]][cur_col+dc[i]]>cost+graph[cur_row+dr[i]][cur_col+dc[i]]:
                if graph[cur_row+dr[i]][cur_col+dc[i]]==0:
                    q.appendleft([cur_row+dr[i],cur_col+dc[i]])
                else:
                    q.append([cur_row+dr[i],cur_col+dc[i]])
                visited[cur_row+dr[i]][cur_col+dc[i]]=cost+graph[cur_row+dr[i]][cur_col+dc[i]]
            if cur_row+dr[i]==n-1 and cur_col+dc[i]==m-1:
                print(cost+graph[cur_row+dr[i]][cur_col+dc[i]])
                is_end=True
                break
        if is_end:
            break

1x1을 처리하는 로직이없었다.

확실히 bfs라면 appendleft방식이 더 어울린다.