백준 1976

<여행 가자>

난이도: 골드 4

1. 백준 문제
   1976

2. 코드 알고리즘

3. 코드

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())

city = [[0 for _ in range(N+1)]for _ in range(N+1)]

def find(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]

def union(a,b):
    parent_a = find(a)
    parent_b = find(b)
    parent[parent_a] = parent_b

for i in range(1, N+1):
    city[0][i] = i
    city[i][0] = i
    a = list(map(int, input().split()))
    for j in range(len(a)): 
        city[i][j+1] = a[j]

route = [0] 
b= list(map(int, input().split()))
for i in range(M):
    route.append(b[i])
    
parent = [0]*(N+1) 
for i in range(1, N+1):
    parent[i] = i


for i in range(1, N+1):
    for j in range(1, N+1):
        if city[i][j]:
            union(i, j) 

pivot = find(route[1])
for i in range(2, len(route)):
    if find(route[i]) == pivot:
        check =1
    else:
        check = 0
        break

if check :
    print("YES")
else:
    print("NO")

4. 코드 후기

이 문제를 풀때는 책의 힌트와 슈도코드를 적극 참조ㅎㅎ
혼자서 city랑 parent 리스트를 상상하고 연결짓기에 어려웠다...
애를 먹었던 부분은 len(b)라고 오타 낸거?

그리고 2개의 for문을 하나의 마지막 for문으로만 줄일 수 있었음!
그래서 마지막 for문에 pivot 하나만 설정하고
route리스트와 비교만 하는 식으로 변경!

내 코드에서 아쉬운 점은
union(i, j) 시행시 union(j,i)는 생략가능한데
이걸 반영하지 못했다는 점?
런타임이 많이 줄을 수 있을 거라 생각...