문제

링크-> https://www.acmicpc.net/problem/1976

풀이

문제 설명
한국에 도시가 N개 있고 도시끼리는 길이 있을수도 없을 수도 있다.
이 때 동혁이의 여행일정 경로가 입력으로 주어졌을 때 여행경로가 가능한지
출력하는 문제이다.

조건으로는 ....
중간에 다른 노드를 여러번 방문하는 경로여도 상관없다 즉
입력으로 받은 여행경로가 연결되어 있는 노드라면 상관없을 듯하다.

입력
첫째 줄에 도시의의 N이 주어진다 (N <= 200)
둘째 줄에 여행 계획에 속한 도시의 수 M이 주어진다.(M <= 1000)
다음 N개의 줄에는 N개의 정수가 주어진다.
i번째 줄에 j번째 수가
1이면 i노드와 j노드가 연결돼있는 것이고
0이면 i노드와 j노드가 연결돼어있지 않다.

출력
가능하다면 YES출력 불가능이면 NO출력해준다.

코드

import sys
input = sys.stdin.readline

N = int(input().rstrip())
M = int(input().rstrip())

graph = [[0] * (N) for _ in range(N)]

for i in range(N):
  graph[i] = list((map(int, input().split())))

for i in range(N):
  for j in range(N):
    if(i != j):
      graph[i][j] = graph[j][i]



def find_parent(parent, x):
  if x != parent[x]:
    parent[x] = find_parent(parent, parent[x])
    return parent[x]
  return x
  
def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  if(a < b):
    parent[b] = a
  else:
    parent[a] = b
#연결되는 노드 유니온 연산 해주기
parent = [0] * (N+1)
for i in range(N):
  parent[i] = i

for i in range(N):
  for j in range(N):
    if(graph[i][j] == 1):
      union_parent(parent, i+1, j+1)

#계획 경로 입력받기
plan = list(map(int, input().split()))
root = []
for i in plan:
  root.append(find_parent(parent, i))

#플랜에 있는 모든노드이 루트노드는 key노드가 나와야 가능한 계획
key = find_parent(parent, plan[0])

result = True
for i in root:
  if key != i:
    result = False

if(result == True):
  print('YES')
else:
  print('NO')

다른 사람들의 코드를 보고난 후

2가지 아이디어를 볼 수 있있다.

1. 어차피 유니온 과정에서 각 노드들의 루트노드를 확인하므로 각 노드들의 부모노드는 루트노드이다. 따라서 마지막에 다시 find함수 호출을 하지말고 parent리스트만 확인해도 됐었다!!!!

2. 두번째는 리스트에서 같은 원소가 있는지 set함수를 이용해서 확인할 수 있었다.
   ex)

   a_list = [1,1,2,3,1]
   #이렇게 리스트가 있을때 set함수를 이용하면 몇개가 다른원소가 있는지 알 수 있다.
   print(len(set(a_list)))
   #만약 리스트에 다른 원소가 없다면 1이 출력될 것이다.