[SWEA 코딩] S/W 문제해결 응용 보급로 - PYTHON #1249

소스 코드

def bfs():

    # temp에 시작 위치(0,0) 저장
    temp = [[0,0]]

    # temp가 빌 때까지 반복
    # == (n-1,n-1)의 값을 구할 때까지
    while len(temp):
        i,j = temp.pop(0)

        for q in range(4):
            ni = i + x[q]
            nj = j + y[q]

            # 범위 제한 조건 안 넘기면
            if 0 <= ni < n and 0 <= nj < n:

                # 이동하려는 위치까지 이동하는 데 소요된 복구 작업의 시간이
                # 현재 위치까지 소요된 복구 작업 시간 + 이동하려는 위치에서 소요되는 작업 시간보다 크면
                # 값 바꾸고, temp에 [ni,nj] 추가
                if check_board[ni][nj] > check_board[i][j] + board[ni][nj]:
                    check_board[ni][nj] = check_board[i][j] + board[ni][nj]
                    temp.append([ni,nj])

    return

x = [0,0,-1,1]
y = [-1,1,0,0]

T = int(input())

for tc in range(1,1+T):
    n = int(input())

    board = [list(map(int,input())) for _ in range(n)]

    # 90000인 이유는 최대 100*100 배열이고
    # 해당 배열을 모두 방문해도 9 * 10000이기 때문
    check_board = [[90000]*n for _ in range(n)]
    
    # 시작 위치 0으로 만들기
    # 0 아니면 출발이 안 됨
    check_board[0][0] = 0

    bfs()

    print('#{} {}'.format(tc,check_board[n-1][n-1]))

 

---

해결 방법

1. 배열의 최대 크기가 100*100이므로 dfs나 bfs로는 해결이 어렵다고 판단

 

2. 다익스트라 알고리즘을 활용해서 문제 해결

다익스트라) 거리 이동에 필요한 최소한의 비용(?)을 찾는 데 유용

예시 ) 

0 2 3

3 4 5

1 2 3

이란 배열이 있을 경우,

 

[0,1]까지 이동에 필요한 최소 값은 2 [1,0]까지 이동에 필요한 최소 값은 3이다.

이를 새로운 3*3 배열에 작성하면

0 2 0

3 0 0

0 0 0

처럼 표현 가능

 

다시 [0,1]에서 [0,2],[1,1]로 이동하는 경우와 [1,0]에서 [2,0],[1,1]로 이동하는 경우를 배열에 작성하면

0 2 2

3 2 0

3 0 0

 

해당 경우에서 [1,1]은 [0,1]과 [1,0] 모두에서 이동이 가능한 위치이기 때문에

더 저렴한 비용을 선택하는 것(2 < 3)

 

---

느낀 점

 

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.