[BOJ] 4485. 녹색 옷 입은 애가 젤다지?(Python) / BFS

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

골드 4 문제인데 체감은 실버 1정도 되는 어렵지 않은 문제였다.

N * N 맵의 (0, 0)위치에서 (N-1, N-1) 위치까지 가는데, 맵에 있는 값들을 더하며 이동한다면 목적지까지 도달하는 최솟값을 구하라.

문제 보자마자 BFS를 떠올렸고, 디버깅 없이 한 번에 코드를 짜서 pass를 받았다.

# 30분 소요

• 사용 알고리즘 : BFS 너비 우선 탐색
• 일반적인 BFS 함수로, visited를 만들어 해당 위치까지 갈 수 있는 최솟값을 표시하는 용도로 사용했다.
• tc별로 while문 내에서 N과 이차원 배열 A를 받는다.
• 함수 내에서 첫 방문일 때는 (현 위치 값 visited[r][c] + 다음 위치 A[nr][nc]) 해준 값으로 표시하고 큐에 담았다.
• 이미 방문한 적이 있다면, 해당 위치를 최솟값으로 갱신할 수 있을 때만 위와 같이 (현 위치 값 + 다음 위치 값)한 것을 표시하고 또 검사해주기 위해 큐에 담아줬다.
• 큐에 있는 모든 원소에 대한 검사가 끝나 while문이 끝나면 visited가 해당 위치까지 갈 수 있는 최솟값을 의미하므로
• 목적지인 visited[nr][nc]에 있는 값을 리턴하고 출력한다.
• N = 0이면 종료한다.

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline
from collections import deque

# 상하좌우
dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

def bfs():
    visited = [[-1] * N for _ in range(N)]
    visited[0][0] = A[0][0]
    Q = deque([(0, 0)])
    
    while Q:
        r, c = Q.popleft()
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if not (0 <= nr < N and 0 <= nc < N):
                continue
            # 첫 방문
            if visited[nr][nc] == -1:
                visited[nr][nc] = visited[r][c] + A[nr][nc]
                Q.append((nr, nc))
            # 이미 누가 방문했다면 해당 위치를 최솟값으로 갱신할 수 있는 경우만 큐에 담는다.
            elif visited[nr][nc] > -1:
                if visited[nr][nc] > visited[r][c] + A[nr][nc]:
                    visited[nr][nc] = visited[r][c] + A[nr][nc]
                    Q.append((nr, nc))

    return visited[N-1][N-1]

tc = 0
while True:
    N = int(input())
    if N == 0:
        break
    A = [list(map(int, input().split())) for _ in range(N)]
    tc += 1
    print("Problem {}: {}".format(tc, bfs()))

---

• 시간 : 208ms / 메모리 : 127716kb
• 고찰 : 문제 이름이 재밌어서 볼 때마다 풀어보고 싶었는데, 결국 풀었다 ㅋㅋ 그것도 30분만에 한 번에 풀어서 기분좋았당. BFS 알고리즘 공부하기 좋은 문제인 것 같다! 요새 BFS 특훈하고 있는데 감이 많이 잡혔다. 문제 푸는 속도가 점점 빨라진다.
• 주말인데 비가 온다.. 알고리즘 문제나 풀어야지~~~