[Python] 백준 16562 친구비, 백준 1976 여행 가자

1. 문제 - 백준 16562 친구비

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

 

💡알고리즘 - DFS or 유니온파인드

- "친구의 친구는 친구다" 즉, 친구 무리를 짓는다는 점에서 DFS 혹은 유니온파인드를 이용할 수 있다.

- 각 친구 무리 별로 친구비가 가장 적은 친구비를 합쳐 준석이가 가진 비용과 비교한다.

 

✅ DFS 풀이

import sys
sys.setrecursionlimit(10**8)

n, m, k = map(int, input().split())
money = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
for _ in range(m):
  v, w = map(int, input().split())
  graph[v].append(w)
  graph[w].append(v)

def dfs(node):
  global temp
  
  visited[node] = True
  temp = min(temp, money[node])

  for i in graph[node]:
    if not visited[i]:
      dfs(i)

answer = 0

visited = [False] * (n+1)
for i in range(1, n+1):
  if not visited[i]:
    temp = 1e9
    dfs(i)
    answer += temp

if answer <= k:
  print(answer)
else:
  print("Oh no")

 

- 친구의 친구는 친구다 --> 같은 친구 그룹을 형성하는 친구 중에 최소 비용을 가진 친구에게 친구비를 주면 된다.

- dfs로 같은 친구 무리들끼리 방문처리하며 무리 내부에서의 temp 라는 친구비 최소값을 갱신하고, answer에 더해나간다.

 

✅ 유니온파인드 풀이

n, m, k = map(int, input().split())
money = [0] + list(map(int, input().split()))
answer = 0
parent = [i for i in range(n+1)]

def find(x):
  if parent[x] == x:
    return x

  parent[x] = find(parent[x])
  return parent[x]

def union(x, y):
  root_x = find(x)
  root_y = find(y)
  
  if money[root_x] > money[root_y]:
    parent[root_x] = root_y
  else:
    parent[root_y] = root_x

for _ in range(m):
  v, w = map(int, input().split())
  union(v, w)

for i in range(1, n+1):
    if i == parent[i]:
        answer += money[i]
    
if answer <= k:
  print(answer)
else:
  print("Oh no")

 

- union 함수: 친구와 친구끼리 무리를 만드는 (부모 노드를 같게 하는) 함수인데, 친구 비용이 제일 작은 친구를 부모 노드로 만들어야하므로 친구 비용이 큰 친구의 부모 노드를 친구 비용이 작은 친구의 부모 노드를 만드는 방식으로 union을 실행한다.

 

2. 문제 - 백준 1976 여행 가자

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

 

💡알고리즘 - 유니온파인드

- 도시들간의 연결 여부가 주어지고, 여행 계획에 속한 도시들을 차례대로 방문할 수 있는지 확인 -> 같은 그룹인지 확인

- 같은 그룹인지 확인하려면? find를 통해 부모 노드를 찾아 union을 통해 같은 집합으로 묶어준다.

 

✅ 풀이

n = int(input())
m = int(input())
graph = [[]]
for _ in range(n):
  graph.append([0] + list(map(int, input().split())))
cities = list(map(int, input().split()))
parent = [i for i in range(n+1)]

def find(x):
  if parent[x] == x:
    return x

  parent[x] = find(parent[x])
  return parent[x]

def union(x, y):
  root_x = find(x)
  root_y = find(y)
  
  if root_x > root_y:
    parent[root_x] = root_y
  else:   # 반대 케이스
    parent[root_y] = root_x

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

x = find(cities[0])
answer = "YES"
for city in cities[1:]:
  if parent[city] != x:   # 위에서 union을 통해 집합을 합쳤을 때, 루트노드가 다르다면 해당 경로대로 방문할 수 없다는 의미임
    answer = "NO"
    break

print(answer)

 

- 도시의 번호가 1부터 N까지 차례대로 주어지므로, union시 연결관계가 있는 노드끼리 부모노드가 더 작은 그룹끼리 합쳐준다.

- 그리고 첫번째 도시의 부모노드 x와 다른 도시들의 부모 노드가 다르다는 것은, 같은 그룹에 있는 경로가 아니므로 방문할 수 없다. 따라서 이때 NO를 출력한다.