[Python Algorithm] 보급로 SWEA #1249

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

내 문제 풀이

import math
from collections import deque

tc = int(input())
INF = math.inf

for t in range(tc):
    n = int(input())
    mapArr = [list(map(int, list(input()))) for _ in range(n)]
    visited = [[INF for _ in range(n)] for _ in range(n)]
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    def bfs(deq, visited):
        while deq:
            (x, y, sums) = deq.popleft()

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if nx < 0 or ny < 0 or nx >= n or ny >= n or (nx, ny) == (0, 0) or visited[nx][ny] <= mapArr[nx][ny] + sums:
                    continue

                visited[nx][ny] = mapArr[nx][ny] + sums
                deq.append((nx, ny, visited[nx][ny]))
        return visited[-1][-1]

    deq = deque()
    deq.append((0, 1, mapArr[0][1]))
    deq.append((1, 0, mapArr[1][0]))
    print("#" + str(t + 1) + " " + str(bfs(deq, visited)))

👉 BFS, 다익스트라 문제 !

 

[변수 설명]

• mapArr는 입력되는 지도 값을 int형 2차원 리스트로 받아준다.
• visited는 bfs 함수를 돌릴 때 방문 여부를 체크해주는 동시에,
  해당 자리까지 오는데 걸린 최솟값을 업데이트해주는 역할을 한다.
  => 여기서 사용한 INF는 아~주 큰 값이므로, 최솟값 갱신에 유용하다.
• dx, dy는 bfs 함수에서 상하좌우로 움직이는 것을 돕는다.

[풀이 설명]

• bfs함수에서 탐색할 자리들을 저장해줄 장소를 deq으로 만들어주었다.
  그리고 가장 먼저 탐색이 시작되어야 할 [0][1], [1][0]에 대한 좌표값과,
  그 자리까지 오는데 걸린 최솟값을 함께 튜플 형태로 저장했다.
• deq에 저장된 첫 번째 요소부터 탐색을 시작하는데,
  그 값을 x, y, sums에 차례대로 저장해서 사용해주었다.
• 앞서 정의한 dx, dy와 for문을 이용하여 상하좌우를 탐색해주는데,
  1) 탐색할 자리가 지도의 범위를 벗어나거나
  2) 시작지점이거나
  3) 이미 visited[nx][ny]에 저장된 값이 충분히 작은 경우
  이렇게 세 경우에는 더이상 탐색할 수 없거나, 탐색할 이유가 없으므로 continue 해준다.
• 위의 3)번 항목에 대해서만 추가로 설명해보자면
  visited[nx][ny]에 INF가 아닌 값이 저장되어있다는 것은 이미 한 번 방문한 적 있다는 의미이고,
  그 값이 탐색하려는 자리 mapArr[nx][ny]의 값과, 현재 mapArr[x][y]까지 오는데 걸린 값보다
  더 작다면, 이미 현재 탐색중인 경로는 최소가 아님이 판명되므로 위와같은 예외 상황을 만들었다.
• 그리고 예외에 걸리지 않았다면 visited[nx][ny]가 방문된 적 있더라도
  현재 탐색하는 경로가 최소라는 의미이므로 visited 리스트를 갱신해주었고,
  deq에는 또 새로운 탐색 필요 좌표에 대한 정보를 추가해서 반복이 진행될 수 있게 했다.
• 마지막에는 visited의 마지막 자리에 저장된 값을 사용하여 도착점에 갈 수 있는 최솟값을 반환했다.

 

💡 피드백

• 처음엔 deque를 사용하지 않고 idx 변수를 만들어서 수동으로 인덱스를 옮겨가며
  while 반복이 진행될 수 있도록 했는데, 이 경우 수가 너무 커지면 시간 초과가 발생했다.
  따라서 deque로 풀이했더니 바로 통과,,!
• 이전까지는 뭔가 라이브러리 많이 사용하는게 싫어서
  deque대신 인덱스 값을 이용하는 방법을 주로 썼었는데,
  앞으로는 deque도 애용해봐야겠다. 더 자세히 공부도 해보고 !