[BOJ]1976(python)

BOJ - 1976(여행가자) python 풀이

어떻게 풀 지 생각

맨 처음에는 dfs를 이용해서 연결 여부를 구하고,
node visited, edge visited 여부를 체크해서 진행하면 되겠다고 생각했다

그런데 visited를 각각 체크하는 것이 아니라 전체 경로에 대해서 한번에 체크하다보니, 방문하지 않은 edge나 노드도 방문처리가 되는 경우가 있었다

반례는 여기서 같은 경우가 있어서 슥삭 해보았다

아무튼 그래서 dfs로 풀이하는 방법 말고 다른 방법을 사용하기로 했다

(dfs 풀이 잘가!)

다음 방법은 플로이드 워셜

플로이드 워셜은 모든 노드간의 최단경로를 구하는 방식이다
시간 복잡도가 O(n^3)이나 될 수 있지만

이 아래의 말 덕분에 사용할 수 있다고 생각했다

시간 복잡도 8000000이면 그럭저럭 돌아갈만 하다 하하

코드

import sys 
input = sys.stdin.readline

from collections import defaultdict

def solution():
    N = int(input())
    M = int(input())
    D = defaultdict(lambda : defaultdict(lambda : float('INF'))) #distance

    for i in range(N):
        temp = list(map(int, input().split()))
        for j in range(N):
            if temp[j] == 1:
                D[i + 1][j + 1] = 1
                D[j + 1][i + 1] = 1

    P = list(map(int, input().split())) 

	#플로이드 워셜
    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i + 1][j + 1] = min(D[i + 1][j + 1], D[i + 1][k + 1] + D[k + 1][j + 1])
    
    for i in range(M - 1):
        start, end = P[i], P[i + 1]
        if D[start][end] == float('INF') and start != end:
            return "NO"

    return "YES"

print(solution())

1. 모든 D 값을 최대 값으로 초기화 해준다(float('inf')
2. 이후 노드 간 연결이 되어있다면 거리를 1로 초기화해준다
3. 플로이드 워셜을 이용해 노드 간의 거리를 구한다
4. 이제 경로를 2개씩 출력하여(start, end), 시작 지점과 도착 지점의 거리를 확인한다
   • 이 때 거리가 float('inf')라면 연결이 되어있지 않은 것이므로 "NO"를 return
   • start와 end node가 같은 경우는 자기 자신이므로 연결이 되어있는 것으로 했다
5. 경로에 따라 모두 연결이 되어있다면 "YES"를 return한다