[백준/BOJ] 백준 코딩 알고리즘 1976번 여행 가자 Python (유니온 파인드)

여행 계획은 간단하게 짜서 가자 친구야

 

 

첫 번째 풀이

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
M = int(input())
roots = [i for i in range(N)]

def find(n): # 루트 노드 찾기
  if roots[n] == n:
    return n
  else:
    root = find(roots[n])
    roots[n] = root
    return roots[n]

def union(i, j): # 한 집합으로 연결하기
  root_i = find(i)
  root_j = find(j)

  if root_i == root_j:
    return

  if root_i > root_j:
    roots[root_i] = root_j
  else:
    roots[root_j] = root_i

for i in range(N):
  roads = list(map(int, input().split()))
  for j in roads:
    if j:
      union(i, j)

trips = list(map(int, input().split()))
trip_roots = []
for i in trips:
  trip_roots.append(find(i-1))

if len(set(trip_roots)) == 1: # 루트 노드가 1개면 어디든지 이동 가능
  print("YES")
else:
  print("NO")

전반적인 설계는 다음과 같다

기본 가정: 여행 경로를 그래프로 생각했을 때, 루트만 연결되어 있으면 어떻게든 갈 수 있다!

이를 기반으로 각 노드에서 루트를 저장하고 이를 비교하는 방식으로 풀이하였다 (유니온 파인드)

 

첫 번째의 풀이는 설계는 맞다고 생각했는데 86%에서 계속 틀렸습니다 가 뜨고 반례를 못찾았다 ㅇ<-<

 

두 번째 풀이

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
M = int(input())
roots = [i for i in range(N)]

def find(n):
  if roots[n] == n:
    return n
  else:
    root = find(roots[n])
    roots[n] = root
    return roots[n]

def union(i, j):
  root_i = find(i)
  root_j = find(j)

  if root_i == root_j:
    return

  if root_i > root_j:
    roots[root_i] = root_j
  else:
    roots[root_j] = root_i

for i in range(N):
  roads = list(map(int, input().split()))
  ##########################
  for j in range(N):
    if roads[j] == 1:
      union(i, j)
  ##########################

trips = list(map(int, input().split()))
trip_roots = []
for i in trips:
  trip_roots.append(find(i-1))

if l(set(trip_roots)) == 1:
  print("YES")
else:
  print("NO")

팀원에게 도움..! 을 요청해서, 오류가 나는 것 같은 부분 (주석으로 감싸진 부분)을 찾았다

그래서 오류의 원인을 파악해보니 다음과 같았다

 

첫 번째 풀이

- j가 직접 길의 유무 값을 저장한 리스트에 접근한다

- 즉, j는 길의 유무 정보를 의미하는 0 또는 1의 값을 갖게 된다

- 길의 유무 값을 의미하는 j를 바로 사용하여 union을 진행한다 -> 오류 발생!!! 길의 유무 값은 union 적용 여부를 판단 요소로만 사용해야 하고, union을 진행할 때는 index 값을 사용해야한다! (하지만 인덱스 값이 아닌 길의 유무 값인 1이 들어가게 되는 것)

 

두 번째 풀이

- j가 range를 사용하여 범위 값을 갖게 된다 (0 ~ N-1)

- j를 인덱스로 사용하여 길의 유무 값을 저장한 리스트(roads)에 접근한다 

- j를 인덱스로 사용하여 접근한 길의 유무 값이 1일 때 union을 진행한다 (정상동작)

 

막상 해결하고 보니까, 사고의 오류,, 논리 오류였다..!

이런 논리 오류에 빠졌을 때 가장 빠져나오기가 어려운 것 같다 😅😢

 

그래도 갓갓 팀원의 도움 덕분에 금방 해결했다!!! 와자뵤!! 감사감사합니다

다음부터는 인덱스 접근이 의도하고 설계한대로 되는지 차근차근 확인해보는 습관을 들여야겠다 (코드를 짤때부터..)