문제

https://www.acmicpc.net/problem/1976

문제접근

• 도시와 도시를 잇는 길이 있다는 점에서 그래프를 생각했다.
• 여행 경로가 존재하는지를 탐색하는 것에서 BFS/DFS를 생각했다. 다른 도시를 경유해서 가도 상관없다는 점이 조금 걸렸다.
• 도시의 수가 최대 200이고 이어진 길의 최대가 1000이라서 플로이드 워셜을 떠올렸다.
• 최단 경로가 아니지만 시간 복잡도 상 가능하고 0과 1로 연결성만 따지면 구현이 쉬울 것 같아서 플로이드 워셜 알고리즘으로 풀려 했다.

코드

from sys import stdin
input = stdin.readline

def main():
    n = int(input())
    m = int(input())
    city = []
    for i in range(n):
        city.append(list(map(int, input().split())))
    p = list(map(int, input().split()))
    for i in range(n):
        for j in range(n):
            for k in range(n):
                city[j][k] = city[j][k] or (city[j][i] and city[i][k])
    for i in range(len(p) - 1):
        s = p[i] - 1
        e = p[i + 1] - 1
        if city[s][e] == 0 and s!=e:
            return "NO"
    return "YES"

print(main())

복잡도 분석

시간 복잡도

플로이드 워셜이라 O(n^3)이다.
채점결과 : 392ms

공간 복잡도

n개의 도시에 대해 각각 다른 도시와의 연결을 2차원 행렬로 나타내야해서 O(n^2)의 공간 복잡도가 필요하다.
채점 결과 : 31120KB

학습포인트

from sys import stdin
input = stdin.readline

def main():
    n = int(input())
    m = int(input())
    city = []
    for i in range(n):
        city.append(list(map(int, input().split())))
    p = list(map(int, input().split()))
    for i in range(n):
        for j in range(n):
            for k in range(n):
                city[j][k] = city[j][k] or (city[j][i] and city[i][k])
    for i in range(len(p) - 1):
        if city[p[i] - 1][p[i + 1] - 1] == 0:
            return "NO"
    return "YES"
    
print(main())

처음에 이렇게 풀었는데 75%쯤에서 틀렸다고 했다.
어디가 틀렸는지 전혀 몰라서 인터넷을 찾아보다가 이 블로그 분도 플로이드 워셜로 풀어서 코드를 참고했다.

그런데 아직도 이해가 안가는 부분이 있다.

마지막에 동혁이의 여행 계획이 가능한지
하나씩 확인하는 과정에서

for i in range(len(p) - 1):
        s = p[i] - 1
        e = p[i + 1] - 1

만약 p 리스트에서 s번째와 e번째 경로가 안 이어져있다면
"NO"를 출력하는 과정에서

if city[s][e] == 0 and s!=e:

and s!=e라는 조건이 필요한건지 모르겠다.