SWEA 5250 최소비용 bfs (파이썬)

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

---

풀이 및 해설(주석)

from collections import deque

def bfs(r, c):
    # 0, 0의 visited의 값은 0으로 초기화
    visited[r][c] = 0
    Q = deque()
    Q.append((r, c))
    while Q:
        r, c = Q.popleft()
        for dr, dc in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < N and 0 <= nc < N:
                # Q와 visited에 넣어 줄지 말지 판단의 값을 넣어줄 변수
                val = 0
                # 만약 다음 칸이 지금 칸보다 크면 val에 그 차이를 저장
                if arr[nr][nc] > arr[r][c]:
                    val = arr[nr][nc] - arr[r][c]

                # 만약 다음 칸의 visited가
                # 현재 칸의 수 + 1(다음 칸으로 가려면 1더해주고 가야됨) + 두 칸의 차이보다 작다면, visited에 거리 저장, Q에 추가
                if visited[r][c] + 1 + val < visited[nr][nc]:
                    visited[nr][nc] = visited[r][c] + 1 + val
                    Q.append((nr, nc))

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

for tc in range(int(input())):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]

    # visited는 거리를 저장할 변수임, 일단 큰 값으로 초기화 해줌
    visited = [[1e9] * N for _ in range(N)]
    bfs(0, 0)
    print(f'#{tc+1}', visited[N-1][N-1])

 

---

후기

• 아직 리스트의 다익스트라 등의 개념이 부족해서 dfs, bfs로 풀어야 겠다고 생각
• dfs로 풀고 싶었지만, 구현은 했는데 시간 초과로 dfs로는 풀 수가 없음
• bfs로 전환, 기존 bfs를 사용한 거리 측정은 많이 해봤지만, 그래프와 관련된 알고리즘을 활용해 풀어야 됨
• 일정 조건을 만족하면 visited에 거리 저장 (주석 참조)