그래프 이론(나만 안되는 연애 / G3) - 14621

1. 문제

깽미는 24살 모태솔로이다. 깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다. 미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다.

이 앱은 사용자들을 위해 사심 경로를 제공한다. 이 경로는 3가지 특징을 가지고 있다.

1. 사심 경로는 사용자들의 사심을 만족시키기 위해 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다.
2. 사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서든 모든 대학교로 이동이 가능한 경로이다.
3. 시간을 낭비하지 않고 미팅할 수 있도록 이 경로의 길이는 최단 거리가 되어야 한다.

만약 도로 데이터가 만약 왼쪽의 그림과 같다면, 오른쪽 그림의 보라색 선과 같이 경로를 구성하면 위의 3가지 조건을 만족하는 경로를 만들 수 있다.

이때, 주어지는 거리 데이터를 이용하여 사심 경로의 길이를 구해보자.

 

2. 입력

입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000)

둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다.

다음 M개의 줄에 u v d가 주어지며 u학교와 v학교가 연결되어 있으며 이 거리는 d임을 나타낸다. (1 ≤ u, v ≤ N) , (1 ≤ d ≤ 1,000)

5 7
M W W W M
1 2 12
1 3 10
4 2 5
5 2 5
2 5 10
3 4 3
5 4 7

 

3. 출력

깽미가 만든 앱의 경로 길이를 출력한다. (모든 학교를 연결하는 경로가 없을 경우 -1을 출력한다.)

34

 

4. 코드

- 틀린 풀이

import sys

input = sys.stdin.readline
INF = float("inf")

n,m  = map(int, input().split())
unival = input().split()
route = [[INF] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(m):
  u,v,d = map(int, input().split())  
  if unival[u-1] == unival[v-1]:
    continue
  route[u][v] = min(d,route[u][v])
  route[v][u] = min(d,route[v][u])


def dp(start, val, cnt):
  if cnt == n:
    return val
  r = INF
  for end in range(1, n+1):
    if not visited[end]:
      visited[end] = True
      if route[start][end] != INF:
        d = dp(end, val + route[start][end], cnt+1)
        if r > d:
          r = d
      visited[end] = False 
  return r
  
result = INF
for i in range(1,n+1):
  visited = [False] * (n+1)
  visited[i] = True
  result = min(result,dp(i,0,1))

print(result)

 

- 맞는 풀이

import sys

input = sys.stdin.readline
n,m  = map(int, input().split())
unival = input().split()
route = []
parent = list(range(n+1))

for _ in range(m):
  u,v,d = map(int, input().split())  \
  # 성별이 같으면 skip
  if unival[u-1] == unival[v-1]:
    continue
  route.append((d,u,v))

# 거리가 짧은 순으로 정렬
route.sort()

# 최상위 노드를 찾는다.
def get_parent(x):
  if x == parent[x]:
    return x
  parent[x] = get_parent(parent[x])
  return parent[x]

# 최상위 노드가 같으면 TRUE 다르면 FALSE 반환
def find_parent(a,b):
  a, b = get_parent(a), get_parent(b)
  # 부모노드가 같지 않다면 이어지지 않았다
  if a == b:
    return True
  else:
    return False

# 최상위 노드를 비교하고 지정한다.
def union_parent(a,b):
  a, b = get_parent(a), get_parent(b)
  if a > b:
    parent[a] = b
  else:
    parent[b] = a
  
cnt = 0
result = 0

for d,s,e in route:
  if not find_parent(s,e):
    union_parent(s,e)
    result += d
    cnt += 1

if cnt == n-1:
  print(result)
else:
  print(-1)

 

5. 풀이설명

① 학교의 수 n, 도로의 개수 m과 남초 대학교 unival 리스트를 입력받는다.

 

② route 배열을 생성하고 0 ~ n+1까지의 배열 parent를 생성한다.

 

③ m 길이의 for문을 실행하는데 u,v,d를 입력받는다.

 

④ unival[u-1]과 unival[v-1] 성별을 비교하여 같으면 continue 아니면 route에 d,u, v를 route에 추가한다.

 

⑤ route 배열을 sort 메소드로 정렬한다.

 

⑥ route 만큼 for문을 실행한다.

 

⑦ find_parent가 false이면 union_parent메소드에 출발점 s와 도착점 e를 인자로 실행하고, result에 거리 d만큼 더하고 도로 수 cnt를 1만큼 더한다.

 

＃ get_parent(x)

- x가 parent[x]와 같을경우 : x를 반환

- x가 parent[x]와 다를경우 : parent[x]를 인자로 get_parent() 함수를 실행(재귀함수)하여 parent[x]에 대입하고 반환

 

＃ find_parent(a,b)

a와 b의 get_parent() 결과가 같을 경우 True 다를 경우 False 반환

 

＃ union_parent(a,b)

a와 b의 get_parent() 결과 a가 b보다 클 경우 parent[a] = b, 반대의 경우 parent[b] = a

 

⑧ 반복문 결과 도로의 개수 n-1과 cnt가 같으면 결과값 result를 반환 다르면 -1을 반환한다.

 

6. 느낀점

처음에는 다익스트라 알고리즘으로 문제를 접근하여 풀었는데 연습문제의 답은 나왔으나 시간초과였다. 구글링 후 크루스칼 알고리즘을 사용하여 풀었다. 크루스칼 알고리즘 풀이를 외우자!!