[SWEA] 보급로(1249) - Python(BFS/다익스트라)

입력 받은 지도에서 최단 거리를 구하여 출력하는 문제이다.

 

SW Expert Academy

---

테스트 케이스

 

[TC1]

입력 :

4

0100
1110
1011
1010

출력 : 2

 

[TC2]

입력 : 

6

011001
010100
010011
101001
010101
111010

출력 : 2

---

해결 과정

처음 문제를 DFS로 풀었지만, SWEA 홈페이지에서는 메모리 초과로 떴다. 그래서 BFS로 접근하여 최단 거리를 구하는 알고리즘인 다익스트라를 이용했다.

 

---

코드

T = int(input())
 
def bfs(j, i):
    global visited, map_, dx, dy, N
 
    visited[j][i] = 0
    queue = []
    queue.append((j, i))
 
    while queue:
        y, x = queue.pop(0)
 
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N: # 범위 안이고
                if visited[ny][nx] > visited[y][x] + map_[ny][nx]: # 더 빠른 경로가 있다면
                    visited[ny][nx] = visited[y][x] + map_[ny][nx] # 해당 경로로 재설정
                    queue.append((ny, nx)) # queue에 넣어줌
 
for test_case in range(1, T + 1):
    N = int(input())
 
    map_ = [list(map(int, input())) for _ in range(N)]
    visited = [[int(1e9)] * N for _ in range(N)]
 
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
 
    bfs(0, 0)
 
    print(f'#{test_case} {visited[-1][-1]}')

 

주석 처리

T = int(input()) # TC 받음
 
def bfs(j, i):
    global visited, map_, dx, dy, N # 전역변수 
 
    visited[j][i] = 0 # 처음 시작은 거리 0
    queue = [] # 큐 생성
    queue.append((j, i)) # 큐에 넣음
 
    while queue: # 큐가 있는 동안
        y, x = queue.pop(0) # 큐의 맨 앞(왼족)에서 하나 빼옴
 
        for i in range(4): # 4방향
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N: # 범위 안이고
                if visited[ny][nx] > visited[y][x] + map_[ny][nx]: # 더 빠른 경로가 있다면
                    visited[ny][nx] = visited[y][x] + map_[ny][nx] # 해당 경로로 재설정
                    queue.append((ny, nx)) # queue에 넣어줌
 
for test_case in range(1, T + 1): # TC 동안
    N = int(input()) # N 받음
 
    map_ = [list(map(int, input())) for _ in range(N)] # map 초기화
    visited = [[int(1e9)] * N for _ in range(N)] # 경로의 거리를 넣을 배열을 생성해서 최대값으로 초기화
 
    dx = [1, 0, -1, 0] # 방향
    dy = [0, 1, 0, -1]
 
    bfs(0, 0) # (0,0)부터 BFS 시작
 
    print(f'#{test_case} {visited[-1][-1]}')