[Python, 파이썬] SWEA 1249. [S/W 문제해결 응용] 4일차 - 보급로

 

출발지(S) 에서 도착지(G)까지 가기 위한 경로 중에
복구 시간이 가장 짧은 경로에 대한 총 복구 시간을 구하는 문제.

 

 

1. DFS

def DFS(i, j, costs):
 
    global min_costs
 
    if not (0 <= i < N and 0 <= j < N): # 0<= x <N 사이에 있지 않을때
        return
 
    if cost_map[i][j] <= costs: # 더 저렴한 경로가 있을 때
        return
 
    if cost_map[N-1][N-1] <= costs: # 현재 탐색 중인 경로가 이전 경로보다 cost가 클 시
        return # 더 탐색하지 않고 종료
 
    cost_map[i][j] = costs # 메모이제이션
 
    DFS(i+1, j, costs+A[i][j]) # 아래로 이동
    DFS(i, j+1, costs+A[i][j]) # 오른쪽으로 이동
    DFS(i, j-1, costs+A[i][j]) # 왼쪽으로 이동
    DFS(i-1, j, costs+A[i][j]) # 위로 이동
     
T = int(input()) # 테스트케이스 수 T
 
for test_case in range(1, T+1):
 
    N = int(input()) # 정수 N
    A = [] # 수열 A
 
    # 수열 입력받기
    for i in range(N):
        A.append(list(map(int, input().strip())))
     
    # 탐색 시작
    cost_map = [[10**10] * N for _ in range(N)] # 메모이제이션
    DFS(0, 0, 0) # 가장 짧은 경로 계산
             
    print("#%d %d" %(test_case, cost_map[N-1][N-1])) 

 

메모이제이션+완전 탐색을 위해 풀 수 있는 문제다.

상하좌우를 봐서 N x N 범위 안에 점점 이동하는데, 이때 현재 탐색 중인 경로가 현재 구한 경로보다 비쌀 시 DFS를 종료한다. 또, 현재 위치에 이전에 더 저렴한 경로를 찾았을 시 그 경로를 update한다.

 

if cost_map[i][j] <= costs: # 더 저렴한 경로가 있을 때
        return

if cost_map[N-1][N-1] <= costs: # 현재 탐색 중인 경로가 이전 경로보다 cost가 클 시
    return # 더 탐색하지 않고 종료

 

 

그러나 DFS를 사용하면 한쪽길로 쭉 가기 때문에 시간이 많이 걸린다.

그래서 Recurison 오류와, 시간초과가 발생할 가능성이 높다.

 

 

 

2. BFS

from collections import deque
 
def BFS(i, j):
 
    q = deque()
    q.append((i, j))
    cost_map[i][j] = 0
 
    dx = [0,1,-1,0]
    dy = [1,0,0,-1]
 
    while q:
 
        x, y = q.popleft()
 
        for i in range(4):
 
            nx = x+dx[i]
            ny = y+dy[i]
             
            if (0 > nx or 0 > ny) or (nx >= N or ny >= N): # 범위를 벗어날 시
                continue
 
            if cost_map[x][y]+A[nx][ny] < cost_map[nx][ny]: # cost_map UPDATE
                    cost_map[nx][ny] = cost_map[x][y]+A[nx][ny]
                    q.append((nx,ny))
     
 
T = int(input()) # 테스트케이스 수 T
 
for test_case in range(1, T+1):
 
    N = int(input()) # 정수 N
    A = [] # 수열 A
 
    # 수열 입력받기
    for i in range(N):
        A.append(list(map(int, input())))
     
    # 탐색 시작
    INF = 10**10
    cost_map = [[INF] * N for _ in range(N)] # 메모이제이션
    BFS(0, 0) # 가장 짧은 경로 계산
             
    print("#%d %d" %(test_case, cost_map[N-1][N-1])) 

 

이거 또한 메모이제이션+완전 탐색으로 푸는 방식이다.

DFS를 BFS로 바꾼 거 뿐인데, 시간이 훨씬 적게 걸린다.

 

DFS는 5,247ms가 걸렸지만 BFS는 221ms밖에 안걸렸다!

사실 왜인지는 모르겠는데 BFS가 인접부분부터 찾는 게 DFS보다 더 빨리 최소의 값을 탐색해서 그런거 같다.