9/6 개인 문제 풀이 - 1

이코테 p393

# 유니온 파인드 알고리즘을 적용하면 풀리겠구나~
import sys

input = sys.stdin.readline

N, M = map(int, input().split())  # 최대 500, 500
graph = []
parent = [i for i in range(0, N + 1)]

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

def union(a, b):
  aParent = getParent(a)
  bParent = getParent(b)

  if aParent == bParent:
    return
    
  if aParent > bParent:
    parent[a] = bParent
  else:
    parent[b] = aParent

graph.append([0] * (N + 1))
for _ in range(N):
  userList = list(map(int, input().split()))
  graph.append([0] + userList)

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

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

before = plan[0]
result = 'YES'

for i in range(1,M):
  if getParent(before) != getParent(plan[i]):
    result = 'NO'
  before = plan[i]

print(result)

# 5 4
# 0 1 0 1 1
# 1 0 1 1 0
# 0 1 0 0 0
# 1 1 0 0 0
# 1 0 0 0 0
# 2 3 4 3

# YES

모든 정점이 연결되어 있어야 즉 한 집합에 포함되어 있어야 여행이 가능하기 때문에 유니온,파인드 알고리즘을 활용하여 풀어냈다.

[i for i in range(0, N + 1)] 이 코드에 노란색 줄이 그어져있어서 왜그런지 살펴보았는데 틀린 코드는 아니고

list(range(0,N+1)로 하면 같은 내용을 간결하게 나타낼 수 있어서 경고가 있었던 것이다. 더 좋은 코드인 것 같다.

9/10 개인 문제 풀이 - 2

이코테 p395

# 유니온 파인드 알고리즘을 적용하면 풀리겠구나~
import sys
from typing import ParamSpecKwargs

input = sys.stdin.readline

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

def union(parent, a, b):  # 나만의 union 이게 더 간단한데?
  if find(parent, a) > find(parent, b):
    parent[a] = parent[b]
  else:
    parent[b] = parent[a]

G = int(input())  # 1 이상 100,000 이하
P = int(input())  # 1 이상 100,000 이하

parent = list(range(0, G + 1))
result = P
flag = 0

for i in range(P):
  g = int(input())
  if flag == 1:
    continue
    
  beforeSet = g-1
  if find(parent, g) == 0:
    result = i
    flag = 1

  # 전 집합을 찾고 union 한다
  for j in reversed(range(0, g)):
    if find(parent, j) != find(parent, g):
      beforeSet = j
      break
  
  union(parent, beforeSet, g)

print(result)

유니온 파인드 알고리즘을 활용해서 풀 수 있다는 것을 떠올리는 것 자체가 어려웠던 것 같다.. 이걸 어떻게 생각하지?! 답지를 보았지만 다시 한번 풀어봤다 해결했다.

아. range 문 거꾸로 적고 싶을떄 resversed를 사용하면 더욱 쉽게 만들수 있었다. step -1 방법도 있는데 reversed가 더 직관적인 것 같다.

그리고 전의 집합을 찾는 방법으로 나는 일일이 찾았는데

그냥 find 함수로 찾은 집합의 -1 해서 전의 루트를 찾으면 그게 전 집합이었다. 이것도 어떻게 떠올리는지는 모르겠지만 어쨌든 그렇게 하면 코드가 더 깔끔해진다. 많이 풀어보자