코딩테스트 백준 5917 PYTHON 나만의 풀이법

코딩테스트를 준비하면서 백준 5917 번 문제를 python 코드로 작성하고 있습니다. 삼성전자 코딩테스트와 카카오 코딩테스트 및 네이버 코딩테스트 시험에 자주 출제되는 BFS 알고리즘을 응용한 문제입니다. 다른 분들이 작성한 코드를 공부하면서 이해가 되지 않았던 내용들을 연구하면서 깨달은 내용들을 조금씩 정리하고 있어요. 백준 5917 문제는 건초 문제로 알려져 있습니다.

목장에서 헛간으로 가는 길은 블록 단위로 구분되어 있습니다. 블록을 행과 열로 지칭하자면 M행 N열의 블록으로 이동할 수 있는 영역이 구분되어 있습니다. 전형적인 BFS 문제로 푸는 문제 같기는 한데 어떻게 문제지에 주어진 조건을 제가 알고 있는 BFS 문제 푸는 템플릿에 어떻게 맞추어 넣을 지가 머리가 아팠습니다. 또상님 블로그를 참고하여 어떻게 풀 것인지 전략을 수립했습니다.

가장 난해한 부분은 최적 경로를 찾은 후에 건조를 그 경로에 배치해서 이동하는데 걸리는 시간을 2배로 만드는 경우에 어떻게 할 것인지 정신이 혼미해졌습니다.

백준 5917 문제 풀이의 뼈대 논리를 세우자!

혼자서 코딩 테스트 문제를 풀라고 머리를 싸메고 있다보면 유튜브를 뒤적이거나 숏츠에 빠져서 시간을 날리기 쉽습니다. 가장 먼저 해야 할 일은 드문 드문 생각나는 아이디어를 일단 메모해 보는 것입니다. 다른 분들이 작성한 코드를 훑어 본 후에 머리에 남는 코드를 나름대로 이해해서 다시 재구성해 보았습니다.

백준 5915 문제풀이 코드

백준 5915 번 문제 풀이 코드는 제가 100% 머리로 짠 코드가 아니라 다른 분들이 작성한 여러 코드를 참고하였으며 또상님 블로그 코드를 공부하면서 깊이 있는 이해를 하기 위해서 제가 첨언을 추가한 것입니다. 이해가 잘못되었을 수도 있으므로 옥석을 가려가시면서 읽어보시면 좋을 것 같습니다.

#baek_joon_5917_test8.py
import sys
from collections import deque
import math


readl=sys.stdin.readline
N,M=map(int,readl().split())
roads=[ list(map(int, readl().split())) for i in range(M)]



def init(roads):
    
    newRoads=roads +[[ end,start,dist] for start,end,dist in roads]
    dict={x[0]:[] for x in newRoads}
    for start, end,dist in newRoads:
        dict[start].append((end,dist))

    dists=[math.inf]*(N+1)

    return dict,dists

def BFS():
    global dict, dists

    # 집은 1
    q = deque([(1, 0)])
    dists[1] = 0

    while q:
        x, dist = q.popleft()

        for nx, d in dict[x]:
            nd = dist + d
            if dists[nx]<=nd:
                continue
            
            q.append((nx,nd))
            dists[nx]=nd
            temppath[nx]=x

    return dists[N]   

max_len=int()
min_len=int()

temppath=[0]*(N+1)


dict,dists=init(roads)
min_len=BFS()


i=temppath[N]
path=list()
dest=N
while i>0:
    path.append((i,dest)) #(출발점, 도착점)
    dest=i
    i=temppath[i]

path=path[::-1]

#print(path)

for i in range(M):
    start,end,dist=roads[i]

    if (start,end) in path or (end,start) in path:
        roads[i][2] *= 2
        dict.clear()
        dict,dists=init(roads)
        temp=BFS()
        #print(temp)
        max_len=max(max_len, temp)
        roads[i][2] /=2

    


print(int(max_len - min_len))

문제 풀이 논리의 재구성

1. init()내부에서 dists배열을 만들어서 최소 경로에 해당하는 경로의 합을 구해서, 최소거리를 구합니다.
2. init()은 dists, dict를 리턴합니다.
3. init 내부에서 dict를 생성합니다. dict={x[0]:[] for x in roads} 표현은 roads에 담긴 여러개의 데이터셋을 딕셔너리로 변환해주는 코드이다.
4. BFS()에서 위치 N지점까지 최소 거리를 가지는 값을 리턴해준다. 여기서는 dists[N]으로 표현된다.
5. 트래킹을 위해서 while i: 문 안에는 path.append((i,dest)) (출발점, 도착점)을 path리스트에 넣어준다.
6. def BFS():
   q.append(( nx , nd))
   path.append((i,dest))
   여기서 dest는 목적지입니다.
   따라서, while i>0:
   path.append((i,dest)) 코드에서 i=temppath[i] 이부분이 중요합니다. 역방향으로 temppath[i]에 해당하는 좌표에 오기전에 어떤 좌표에서 넘어왔는지에 대한 기록이 temppath[]리스트에 기록되어있습니다.
   temppath[]는 BFS() 메서드 내부에서 검증된 nx에 대해서 x값을 저장해서 만들어졌습니다.
7. 즉 temppath[nx]=x 코드의 의미는 이전 지점의 좌표x를 다음 목적지인 nx와 결합하여 저장한다는 의미가 있습니다.
8. while i>0: 구문 안에서 루프를 반복하면서, path.append((i,dest)) 를 넣는것은 path에 저장된 목적지 좌표를 역순서로 저장하기 위함입니다.
9. 그 이후에 i=temppath[i] 를 하는 이유는
   i 지점의 다음 지점을 다시 i로 할당함으로서 while i: 구문이 다음 순서의 원소로 넘어가기 위함입니다. return dists[N]
   여기부터 진짜로 문제를 푸는 부분입니다.
10. for i in range(M):
    M개의 행만큼 반복을 수행합니다.
    

문제 풀이의 기본 틀 만들기

예제 코드를 보면서도 발상의 전환이 잘되지 않는 부분이 있습니다.

for i in range(M): #입력데이터셋이 M행이므로 for문을 M번 도는 것은 자연스럽습니다.

b=BFS( roads) #최단거리 경로를 찾아서 dists[ ] 리스트에 저장해주고 최종적으로 BFS( ) 가 리턴해 주는 값은 메모리 값이 할당된 dict 데이터와 dists[N] 최단거리 데이터값입니다.

if (start, end) in path or (end, start ) in path:


#roads에 저장된(start,end,dists) 들을 양방향으로 만들고 그 중에서 거리를 2배로 높여봅니다.
# 이때 신경 써야 할 부분은 (start, end, dists) 가 아니라 ( start , end ) 라는 점입니다. 거리 값에 해당하는 값은 roads[][2] 입니다. roads[ ][2] 값을 2배로 만들기 위해서 roads[ ][2] *= 2 로 설정합니다.

특히 roads[ ] 리스트에서 데이터셋 ( start, end, dists )을 가져오는 것이 아니라 ( start, end ) 를 path 에서 가지고 오는 점에 유의해야 합니다.


path 리스트는 while i: 구문 안에서 path[ ] 리스트 값을 모두 채워줍니다. 여기서는 path[ ] 에는 역방향으로 정렬된 패스 노드의 번호가 경로의 순서대로 배치가 됩니다. 역방향 정렬하기 전에는 반대 순서로 경로의 노드 번호가 들어가 있었습니다.

아래 구문은 그래서 M행의 입력 데이터셋 중에서 i 번째 행의 경로 데이터 중에서 거리 값만 2배로 증가 시킨다는 의미가 됩니다.

path[i][2] *=2


노드가 거리를 2배로 증가 시킨 이후에 newRoads[ ] 를 새로 생성하고 dict( ) 값도 새로 생성하기 위해서

최단 거리 path 경로를 구하기 위해서 BFS( roads )에 입력하여 최적 경로의 최단거리를 구합니다.

# 최단거리 변수 max_of_second_min 을 for문을 M 번 반복하면서 최소값을 BFS( ) 에서 리턴된 값과 비교하여 업데이트 합니다.

max_of_second_min = max( max_of_second_min, BFS( roads ) )

최종적으로 건조를 최적 경로에 쌓은 후에 찾을 수 있는 가장 작은 지연 시간은 아래와 같습니다. first_min 은 건초더미를 쌓기전에 BFS(roads)에서 리턴한 최적의 경로를 지날 때 걸리는 최소 시간을 의마합니다.

따라서, “최소 시간은 2배로 시간이 걸리도록 셋팅한 시간 – 최단경로에 걸린 시간” 으로 계산할 수 있습니다.

print(int(max_of_second_min)-first_min)

입력 데이터

5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

출력

2

마치며

백준 5917 번 문제를 이해하는데 2주 정도 소요되었습니다. 퇴근 후 2시간 정도 공부하고 주말에는 토요일과 일요일에 도서관에 가서 코드를 읽어보고 직접 작성해보고 했는데 단순히 코드를 외워서 재현하려고 하여도 재현이 되지 않더군요.

전체적으로 어떤 논리로 코드를 작성할 것 인지에 대해서 충분히 생각한 후에 로직을 구성한 후에 각 메서드를 정의하고 코딩 작업을 시작해야 시간을 아낄 수 있습니다. 다음 번에도 코딩 테스트에서 자주 출제되는 문제를 직접 풀어보고 자세하게 설명을 드리도록 하겠습니다.