[백준] 4485번 녹색 옷 입은 애가 젤다지? (파이썬)

 

문제

 

4485번: 녹색 옷 입은 애가 젤다지?

 

 

 

 

정답 소스코드 (Python)

 

from collections import deque
count,dx,dy=0,[0,0,1,-1],[1,-1,0,0]

def bfs():
    queue=deque()
    queue.append([0,0])
    cost[0][0]=field[0][0]
    while queue:

        x,y=queue.popleft()

        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if -1<nx<n and -1<ny<n:
                if cost[y][x]+field[ny][nx]<cost[ny][nx]:
                    cost[ny][nx]=cost[y][x]+field[ny][nx]
                    queue.append([nx,ny])
    return cost[n-1][n-1]


while True:
    n=int(input())
    if n==0:break
    count+=1
    field=[]
    for i in range(n):field.append(list(map(int,input().split())))
    cost=[[1e9 for j in range(n)]for i in range(n)]
    print(f"Problem {count}: {bfs()}")

 

 

풀이  (Python)

 

 

 

문제의 내용은 각 칸을 지날 때 해당 칸의 비용만큼 더해서 최소의 비용으로 오른쪽 아래 field[n-1][n-1]로 도착하는 것이다.

조건은 아래 오른쪽 방향으로만 가기에는 최적의 경로가 최소비용이 아닐 수 있다는 것을 생각해 봐야한다.

모두 탐색을 하며 최단거리 or 최소 비용문제이기 때문에 bfs를 선택하여 풀이하였다.

가는 최단거리를 확인하는 문제가 아닌 최소 비용을 확인하는 문제라고 봐야 한다.

 

 

 

Point 1)  dp와 비슷한 최소 비용 판단방식

 

다음 움직일 수 있는 field칸을 최소비용 결과 리스트인 cost리스트와 함께 조건에 포함시켜 비교를 하는 것이 포인트이다.

if cost[y][x]+field[ny][nx]<cost[ny][nx]:
    cost[ny][nx]=cost[y][x]+field[ny][nx]
    queue.append([nx,ny])

오른쪽 또는 아래쪽으로 만 이동하는 것이 최솟값이 아닌 비용이 더 적은 길이 최솟값이 될 수 있으므로 field에서 추가될 (nx, ny) 값을 현재 cost와 더하여 cost[ny][nx]보다 작다면 해당 칸으로 이동한다.

 

 

 

 

Point 2) 최솟값 갱신을 위한 리스트 초기화

 

지속적으로 결과 리스트인 cost리스트를 최솟값으로 갱신할 것이기 때문에 초기화를 0과 같이 평범한 값이 아닌 나올 수 있는 최댓값보다 큰 수인 1e9을 사용하였다 1e9은 10의 9승과 같다.

 

cost=[[1e9 for j in range(n)]for i in range(n)]