[SWEA] D4. 보급로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=%EB%B3%B4%EA%B8%89%EB%A1%9C&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

1. 해결방법

BFS

1. 모든 경로를 탐색해야하기도 하고, 첫 목적지 까지 계산하고 BFS를 통해 차근차근 탐색한다.
2. 방문체크를 통해서 처음 갈 때와 BFS로 인해 이미 방문된 위치를 나누어서 조건을 단다.
3. new_maps라는 복구 시간 데이터를 새롭게 저장하기 위해 0으로 도배된 2차원 배열을 생성한다.

위의 세 가지만 생각하면 풀 수 있다. 
물론 2번이 꽤 말썽이다. 
어찌됐든 두 가지 방법으로 나누어야 하니까.. 또한 new_maps라는 복구 시간 데이터를 저장한 배열까지 있으니 2개의 2차원 배열을 비교하면서 조건을 달아야 한다.

 

2. 정답코드

from collections import deque

input = sys.stdin.readline

T = int(input())
# T = 1
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N = int(input())
    maps = [list(map(int, input().strip())) for _ in range(N)]

    chk = [[False] * N for _ in range(N)]
    new_maps = [[0] * N for _ in range(N)]
    dy, dx = (1, 0, -1, 0), (0, 1, 0, -1)

    def bfs(y, x):
        global result

        q = deque()
        q.append((y, x))

        while q:
            ey, ex = q.popleft()
            for k in range(4):
                ny, nx = ey + dy[k], ex + dx[k]
                if 0 <= ny < N and 0 <= nx < N:
                    if chk[ny][nx] == False:
                        new_maps[ny][nx] = maps[ny][nx] + new_maps[ey][ex]
                        q.append((ny, nx))
                        chk[ny][nx] = True
                    else:
                        if new_maps[ny][nx] <= new_maps[ey][ex] + maps[ny][nx]:
                            continue
                        else:
                            new_maps[ny][nx] = maps[ny][nx] + new_maps[ey][ex]
                            q.append((ny, nx))



    chk[0][0] = True
    bfs(0, 0)
    print(f'#{test_case} {new_maps[N - 1][N - 1]}')