[오답노트 | 파이썬] 프로그래머스 - 배달

어떻게 풀어야 할지 몰라서 제대로 된 시도조차 하지 못한 문제다.. 맞추지 못한 내용을 올려서 부끄럽지만, 이렇게 박제(?) 해야 다음에는 맞추려고 아등바등할 것 같다.

문제

풀지 못한 이유

• 입력 값 road를 어떻게 사용해야 할지 모르겠다.
• 반복문을 너무 많이 사용하면 시간초과될 것 같으니, BFS로 각 마을을 탐색하면 될 것 같은데 어떻게 코딩해야할지 모르겠다.

풀이 1) 플로이드 워셜 알고리즘 이용

질문하기에 있던 플로이드 워셜을 이용한 풀이 방법이다.

플로이드 워셜이란?

• 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘이다.
• 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다.
• 2차원 테이블에 최단 거리 정보를 저장한다.
• 기본적으로 3중 반복문을 이용해서 2차원 테이블을 갱신하는 방식으로 동작하기에 시간 복잡도는 O(N^3)이다.
• 노드의 개수가 적을 때 효과적으로 사용할 수 있다.

def solution(N, road, K):
    # 2차원 리스트(그래프 표현)을 만들고, 무한으로 초기화(1e9: 무한을 의미하는 값, 10억)
    graph = [[int(1e9) for _ in range(N+1)] for _ in range(N + 1)]

    # 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
    for i in range(1, N+1):
        graph[i][i] = 0

    # 길이 연결된 정보(road)를 통해 길을 지나가는 비용 초기화
    for i, j, c in road:
        graph[i][j] = min(graph[i][j], c)
        graph[j][i] = min(graph[j][i], c)

    # 점화식에 따라 플로이드 워셜 알고리즘 수행
    # k: 반드시 거쳐 지나가는 노드, i: 출발 노드, j: 도착 노드
    for k in range(1, N+1):    
        for i in range(1, N+1):
            for j in range(1, N+1):
                # i->j 최단 거리: 기존값(graph[i][j])과 k를 지나가는 값(graph[i][k] + graph[k][j]) 중에 더 작은 값
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

    # 1번 노드에서 각 노드에 도달하는 비용이 K보다 작거나 같은 것만 골라내기
    ans = [x for x in graph[1] if x <=K]
    return len(ans)

자, 이제 위의 코드를 하나씩 뜯어보자!
먼저 2차원 리스트를 만드는 데, 값은 모두 무한(1e9; 10억)으로 초기화한다.

graph = [[int(1e9) for _ in range(N+1)] for _ in range(N + 1)]

# 무한으로 초기화된 graph 모습
[
    [1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000], 
    [1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000],
    [1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000], 
    [1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000],
    [1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000],
    [1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000]
]

초기화하는 과정에서 자기 자신으로 가는 비용은 0으로 초기화한다.

for i in range(1, N+1):
	graph[i][i] = 0

# 자기 자신으로 가는 비용을 0으로 초기화한 graph 모습
[
    [1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000], 
    [1000000000, 0, 1000000000, 1000000000, 1000000000, 1000000000], 
    [1000000000, 1000000000, 0, 1000000000, 1000000000, 1000000000], 
    [1000000000, 1000000000, 1000000000, 0, 1000000000, 1000000000], 
    [1000000000, 1000000000, 1000000000, 1000000000, 0, 1000000000], 
    [1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 0]
]

⁉️ 제일 첫 번째 행의 첫 번째 열은 왜 0이 아닌 거지..?
1부터 N까지의 마을을 확인할 것이므로 제일 첫 번째 행과 첫 번째 열은 무시한 것이다.

그다음은 길이 연결된 정보(road)를 통해서 길을 지나는 비용을 초기화한다.

for i, j, c in road:
	graph[i][j] = min(graph[i][j], c)
	graph[j][i] = min(graph[j][i], c)

# 각 길을 지나는 비용을 초기화한 graph 모습
[
    [1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000], 
    [1000000000, 0, 1, 1000000000, 2, 1000000000], 
    [1000000000, 1, 0, 3, 1000000000, 2], 
    [1000000000, 1000000000, 3, 0, 1000000000, 1], 
    [1000000000, 2, 1000000000, 1000000000, 0, 2], 
    [1000000000, 1000000000, 2, 1, 2, 0]
]

이제 점화식에 따라서 플로이드 워셜 알고리즘을 수행한다. 위에는 4중 반복문으로 작성되어 있지만, 3중 반복문으로 돌려도 된다.(그게 더 빠르다. 왜 4중으로 작성했는지 모르겠다.🤔)

# k: 반드시 거쳐 지나가는 노드, i: 출발 노드, j: 도착 노드
for k in range(1, N+1):    
	for i in range(1, N+1):
		for j in range(1, N+1):
			# i->j 최단 거리: 기존값(graph[i][j])과 k를 지나가는 값(graph[i][k] + graph[k][j]) 중에 더 작은 값
			graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

만약, 이 부분이 이해가지 않는다면 [이것이 코딩 테스트다 with Python] 31강 플로이드 워셜 알고리즘 영상 참고하기!

문제에서 1번 마을을 기준으로 시간 비용을 체크하기 때문에 1번 노드에서 각 노드에 도달하는 비용이 K 시간보다 작거나 같은 것 만 골라내면 된다.

ans = [x for x in graph[1] if x <=K]

# 결과
[0, 1, 2, 3]

이 결과(ans)의 길이를 return 하면 끝!

return len(ans)

# 총 4개의 마을로 부터 주문을 받을 수 있다는 뜻
4

풀이 1) 회고

플로이드 워셜은 각 노드에서 모든 노드까지의 최단 경로를 구하는 알고리즘인 것을 잊지 말자! 그리고 플로이드 워셜 알고리즘 3중 반복문이 사용되기 때문에 시간 복잡도가 크다. 따라서 노드가 적을 수록 효율적인 것도 잊지 말자!

---

풀이 2) maxsize 이용

다른 사람의 풀이에 있던 방법이다.
sys 라이브러리의 maxsize를 이용하여 최대 정수값으로 초기화하면서 시작한다. 마치 플로이드 워셜에서 무한대로 초기화하는 것과 비슷하다.

# sys: 변수와 함수를 직접 제어할 수 있게 해주는 모듈
# maxsize: 시스템이 저장할 수 있는 정수 최댓값
from sys import maxsize
def solution(N, road, K):
    # visited: 각 마을 방문 여부
    # D: 1번 마을에서 각 마을까지 걸리는 최소 시간 비용
    # r: 각 마을이 연결된 도로 정보 (연결된 마을, 시간시용)
    visited, D, r = [False]*(N+1), [maxsize]*(N+1), [[(None, None)]] + [[] for _ in range(N)]

    # 각 마을이 연결된 정보를 r에 담기
    for e in road:
        r[e[0]].append((e[1],e[2]))
        r[e[1]].append((e[0],e[2]))

    # 1번 마을에서 1번 마을 까지의 시간 비용 초기화 (항상 0)
    D[1] = 0

    # 1번 마을에서 각 마을까지 걸리는 최소 시간 비용 갱신
    for _ in range(1,N+1): 
        min_ = maxsize    # min_ 값은 최대 정수값으로 초기화
        
        for i in range(1,N+1): 
            # 마을에 방문한적 없고, 마을까지 시간 비용이 min_ 보다 작을 때
            if not visited[i] and D[i] < min_:
                # min_ 과 m을 갱신
                min_ = D[i]
                m = i

        # 방문처리
        visited[m] = True

        # 모든 길을 돌면서 최소 시간 비용 갱신
        for w, wt in r[m]:
            # 기존 값(D[w])보다 새로운 값(D[m] + wt)이 더 작으면 시간 비용 갱신하기
            if D[m] + wt < D[w]:
                D[w] = D[m] + wt

    # 시간 비용이 K보다 작거나 같은 것만 세기
    return len([d for d in D if d <= K])

그럼 위의 코드를 살펴보자.
먼저, 변수들을 초기화한다. 각 마을의 방문 여부를 저장할 visited 리스트, 1번 마을에서 각 마을까지의 최소 시간 비용을 담을 D 리스트, 각 마을이 연결된 정보를 튜플로 담은 r 리스트.

여기서 maxsize를 이용해서 초기 시간 비용을 최대 정수값으로 초기화한다. 그리고 1번 마을부터 N번 마을까지 확인할 것이므로 제일 첫 번째(index = 0)는 무시한다.

visited, D, r = [False]*(N+1), [maxsize]*(N+1), [[(None, None)]] + [[] for _ in range(N)]

# 각 변수의 초기화된 모습
visited: [False, False, False, False, False, False]
D: [9223372036854775807, 9223372036854775807, 9223372036854775807, 9223372036854775807, 9223372036854775807, 9223372036854775807]
r: [[(None, None)], [], [], [], [], []]

road 입력값을 이용해서 각 마을이 연결된 정보를 (연결된 마을의 번호, 연결된 길의 시간 비용)의 튜플 형식으로 정리한다.

아래에서 r[1]인 [(2, 1), (4, 2)]는 1번 마을과 연결된 마을의 정보인 것이다.

# 각 마을이 연결된 정보를 r에 담기
for e in road:
	r[e[0]].append((e[1],e[2]))
	r[e[1]].append((e[0],e[2]))

# 정리된 r의 모습
[[(None, None)], [(2, 1), (4, 2)], [(1, 1), (3, 3), (5, 2)], [(2, 3), (5, 1)], [(1, 2), (5, 2)], [(2, 2), (3, 1), (4, 2)]]

그리고 문제에서 1번 마을에서 주문을 받을 수 있는 마을을 찾으라고 했기 때문에 1번 마을에서 1번 마을까지의 시간 비용은 항상 0이 된다.

# 1번 마을에서 1번 마을 까지의 시간 비용 초기화 (항상 0)
D[1] = 0

# D의 모습
[9223372036854775807, 0, 9223372036854775807, 9223372036854775807, 9223372036854775807, 9223372036854775807]

이제 1번 마을에서 각 마을까지 걸리는 최소 시간 비용을 정리한다. 각 마을을 돌면서 아직 방문하지 않았고, 시간 비용이 최소인 마을(m)을 알아낸다. 그럼 그 마을을 방문 처리하고, 아까 정리한 r 리스트에서 마을(m)과 연결된 길을 모두 확인하면서 최소 시간 비용을 갱신한다.

# 1번 마을에서 각 마을까지 걸리는 최소 시간 비용 갱신
for _ in range(1,N+1): 
	min_ = maxsize    # min_ 값은 최대 정수값으로 초기화
        
	for i in range(1,N+1): 
		# 마을에 방문한적 없고, 마을까지 시간 비용이 min_ 보다 작을 때
		if not visited[i] and D[i] < min_:
			# min_ 과 m을 갱신
			min_ = D[i]
			m = i
            
	# 방문처리
	visited[m] = True

	# 모든 길을 돌면서 최소 시간 비용 갱신
	for w, wt in r[m]:
		# 기존 값(D[w])보다 새로운 값(D[m] + wt)이 더 작으면 시간 비용 갱신하기
		if D[m] + wt < D[w]:
		D[w] = D[m] + wt

# D의 모습(1번 마을에서 각 마을까지 걸린 최소 시간)
[9223372036854775807, 0, 1, 4, 2, 3]

마지막으로 정리한 D 리스트에서 K보다 작거나 같은 값만 세어 반환한다.

# 시간 비용이 K보다 작거나 같은 것만 세기
return len([d for d in D if d <= K])

풀이 2) 회고

풀이 1에서는 3중 반복문을 사용하고, 풀이 2에서는 2중 반복문을 사용해서 풀이 1보다 실행 속도가 빨랐다. 그리고 sys.maxsize를 이용해서 무한 값을 정의한다는 것을 이번에 처음 알았다. 또, 이번 코드를 이해하는 데 오래 걸렸다. 문제를 풀 때 실행 속도를 고려해야 하기 때문에 문제를 읽고 최대한 빨리 이해하고 적절한 알고리즘을 생각해 설계하고 구현해야 함을 다시 느꼈다.

💙 참고한 영상
[이것이 코딩 테스트다 with Python] 31강 플로이드 워셜 알고리즘