💬 문제 이해

상근이의여행
상근이가 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수를 출력한다.

비행기 종류 = 간선으로 생각
간선 weight = 1로 생각

🤔 문제를 보고 처음 든 생각

국가들은 네트워크처럼 생겼고, 나라들이 vertex, 비행기들이 edge , 각 edge weight는 1로 쳤을때 MST를 구하면 모든 국가를 여행하기 위해 타야하는 비행기 종류의 최소 갯수가 나오겠구만

🗡 처음 짠 코드

# 특정 원소가 속한 집합 찾기 
def find_parent(parent, x) :
	# 루트노드가 아니라면, 루트노드를 찾을때까지 재귀호출
  if parent[x] != x :
    parent[x] = find_parent(parent, parent[x])
  return parent[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



test_case_num = int(input())

# 테스트 케이스만큼 반복
for _ in range (test_case_num) :

  v, e = map(int, input().split())# 노드의 갯수와 간선(union 연산)의 갯수 입력받기
  parent = [0] * (v+1) #부모 테이블 초기화

  # 모든 간선을 담을 리스트와 최종 비용을 담을 변수 
  edges = []
  result = 0

  # 부모 테이블상에서, 부모를 자기자신으로 초기화
  for i in range(1, v+1) :
  	parent[i] = i

  # 모든 간선에 대한 정보를 입력받기
  for _ in range(e) :
    a, b= map(int, input().split())
    # 비용순으로 정렬하기 위해서 튜플의 첫번째 원소를 비용으로 설정
    edges.append((1, a, b))

  # 간선을 비용순으로 정렬
  edges.sort()

  # 간선을 하나씩 확인하며
  for edge in edges :
    cost, a, b = edge
  # 사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent, a) != find_parent(parent, b) :
      union_parent(parent, a, b)
      result += cost
 
  print(result) # 최종 최소 비용을 출력

  # 재출력을 위해 초기화
  del parent
  del edges
  result = 0

통과!!

😟 불헌듯 등줄기가 싸늘

다시 문제를 읽어보니
근데 이미 방문한 국가도 방문해도 된다면 크루스칼이 아닐텐데
어... 첫번째 시도가 왜 통과했지 아마 시간제한이 더 빡셌더라면 통과못했을 것이다.

다시 생각하면
1. 모든 vertex 방문해야
2. 재방문 가능
3. 최소 edge 종류일때 그 갯수를 출력하시오

검색해본결과 BFS 문제라고 함!
근데 아직까지 BFS가 모든 노드를 방문하는 방법 이라는 생각은 들지만
"모든 노드를 최소한의 edge를 사용해서 방문하는 방법 이라는 생각은 안들어서
먼가 찝찝한 믿기지 않는 약간 불신이 있지만 그렇다고 하니까 받아들이는 그런 표정으로 받아들여야했음.
오늘 벨로그에 BFS DFS 랑 정렬알고리즘 정리해야겠다

🔖 다른 좋은 코드 스크랩

깔끔한 BFS 풀이 를 참고하도록 하자!

✔️ 크루스칼로 풀었을때와 BFS로 풀었을때

크루스칼

BFS

BFS가 12ms 빠르다

• BFS 시간복잡도 : O(V+E)
• 크루스칼 시간복잡도 : O(ElogE) - 정렬시키는데 시간 많이 걸림

오.. 글쿠만..
운이좋아서 널널하게 크루스칼로 통과했다
다음부터 정말 최적의 방식을 생각하도록 하자!
그리고 다시 생각해보면 어차피 weight을 1로 통일시켜놨으니 Edge weight순으로 정렬하지 않아도 괜찮았었다.