1249. [S/W 문제해결 응용] 4일차 - 보급로

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=1 

SW Expert Academy

 

-dfs 풀이
이렇게 풀면 시간 초과가 나와서 bfs로 다시 풀었습니다.

import sys
sys.stdin = open("input.txt")
 
t = int(input())
 
def dfs(start_x,start_y):
    global result
 
    #상하좌우 움직임
    for i in range(4):
        nx = start_x + dx[i]
        ny = start_y + dy[i]
 
        #맵 안에서 움직이기
        if nx >= 0 and nx < n and ny >=0 and ny < n:
            # 구한값이 다른 값보다 작은 경우에만 연산하기
            if temp[nx][ny] > graph[nx][ny] + temp[start_x][start_y]:
                temp[nx][ny] = graph[nx][ny] + temp[start_x][start_y]
                #재귀적 실행
                dfs(nx,ny)
    return
 
for test in range(1,11):
    #맵 크기
    n = int(input())
 
    # nxn맵정보 저장
    graph = [list(map(int, input())) for i in range(n)]
    # nxn 최대값 리스트
    temp = [[1e9 for i in range(n)] for i in range(n)]
    temp[0][0] = 0
    # 이동방향 : 상하좌우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    #결과값 저장 리스트
    dfs(0,0)
    print(f'#{test} {temp[n-1][n-1]}')
 

 

- bfs 풀이

t = int(input())
 
def bfs(start_x,start_y):
    q = [(start_x,start_y)]
 
    while q:
        start_x, start_y = q.pop(0)
        #상하좌우 움직임
        for i in range(4):
            nx = start_x + dx[i]
            ny = start_y + dy[i]
 
            #맵 안에서 움직이기
            if nx >= 0 and nx < n and ny >=0 and ny < n:
                # 구한값이 다른 값보다 작은 경우에만 연산하기
                if temp[nx][ny] > graph[nx][ny] + temp[start_x][start_y]:
                    temp[nx][ny] = graph[nx][ny] + temp[start_x][start_y]
                    q.append((nx,ny))
    return
 
for test in range(1,11):
    #맵 크기
    n = int(input())
 
    # nxn맵정보 저장
    graph = [list(map(int, input())) for i in range(n)]
    # nxn 최대값 리스트
    temp = [[1e9 for i in range(n)] for i in range(n)]
    temp[0][0] = 0
    # 이동방향 : 상하좌우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    #결과값 저장 리스트
    bfs(0,0)
    print(f'#{test} {temp[n-1][n-1]}')

마지막 원소의 값이 최소가 되어야 하므로 각각의 위치값이 최소일 때만 실행시켜서 마지막의 원소만 출력시킵니다.

이때 실시간으로 최소가 되어야 하므로 초깃값을 무한대이라고 할 수 있는 1e9로 초기화시켜야합니다.

지금까지 dfs와 bfs의 개념을 놓치고 문제를 풀고 있어서 다시 정리해보았다.

dfs의 동작 원리는 스택, 방식은 재귀함수이다. 그리고 bfs의 동작원리는 큐,  방식은 큐 자료구조를 이용한다.

이때 어떠한 방법을 사용하는지에 대한 방법은 시작위치가 1곳인가 여러곳인가 이다. 1곳이라면 bfs, 여러곳이라면 dfs가 편리하다.

dfs는 재귀, bfs는 큐를 활용하는 것을 잊지 말자.

그리고 dfs는 모든 곳을 뒤져봐야 할거 같을 때 쓰고, bfs는 각각의 최적을 구하면 될 거 같은 때 쓰면 된다.