파이썬 알고리즘 304번 | [백준 9372번] 상근이의 여행 - MST, 크루스칼, 원리 이론

304. 상근이의 여행

1) 어떤 전략(알고리즘)으로 해결?

• MST / 크루스칼

2) 코딩 설명

<내 풀이>

(1) BFS

import sys
from collections import deque, defaultdict

def bfs(start, plane_cnt) :
    q = deque()
    q.append(start)
    visit[start] =  1
    while q :
        if sum(visit) == N : 
            return plane_cnt
        now = q.popleft()
        for next in relation[now] :
            if visit[next] == 0 :
                q.append(next) # 큐에 넣는다는 것
                plane_cnt+=1 # 비행기에 탄다는 것
                visit[next] = 1 # 그 국가는 방문한다는 것

# 큐에 넣을 때!! 방문처리도 하고, 비행기를 하나 더 쓴다는 것이라서 비행기 +1
T = int(sys.stdin.readline().rstrip())
for _ in range(T) :
    # 비행기의 종류 M
    relation = defaultdict(list) # 이걸 for 문 밖에 두었었습니다. 
    N,M = map(int, sys.stdin.readline().rstrip().split())
    for i in range(M) : 
        a,b = map(int, sys.stdin.readline().rstrip().split())
        relation[a].append(b)
        relation[b].append(a)
    # 국가의 수 N(2 ≤ N ≤ 1 000)
    visit = [ 0 for _ in range(N+1) ]
    # 1번 국가부터 
    print(bfs(1,0))

(2) 이 방법 말고도 MST의 성질을 이용하는 풀이

• 무조건 노드의 갯수 보다 하나 적은 것이 간선의 갯수
  

T = int(sys.stdin.readline().rstrip())
for _ in range(T) :
    # 비행기의 종류 M
    N,M = map(int, sys.stdin.readline().rstrip().split())
    for i in range(M) : 
        a,b = map(int, sys.stdin.readline().rstrip().split())
    print(N-1)
    

< 내 틀렸던 풀이, 문제점>

(1) 메모리 초과 - visit을 매번 copy() 하는 이슈

def  bfs(nation) :
    q = deque()
    q.append((nation, [0 for _ in range(N+1)], 0)) 
    while q :
        now_nation, visit, airplane_cnt = q.popleft()
        visit[now_nation] = 1
        if sum(visit)==N : 
            return airplane_cnt
        for nxt in rel[now_nation] :
            if visit[nxt]==0:
                q.append((nxt, visit.copy(), airplane_cnt+1))

T = int(sys.stdin.readline().rstrip())
for _ in range(T) :
    # 비행기의 종류 M
    N,M = map(int, sys.stdin.readline().rstrip().split())
    rel = defaultdict(list)
    for i in range(M) : 
        a,b = map(int, sys.stdin.readline().rstrip().split())
        rel[a].append(b)
        rel[b].append(a)
    # 상근이가 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수를 출력
    # 국가 : 1 ≤ a, b ≤ n
    min_cnt = 100000
    for i in range(1,N+1) :
        tmp_cnt = bfs(i)
        if type(tmp_cnt)==int : 
            min_cnt = min(min_cnt, tmp_cnt)
    print(min_cnt)

(2) BFS 접근 - 25%에서 틀림 처리

• airplane, visit 수는 실시간 공유되는 것입니다.
• 틀린 원인

  relation = defaultdict(list) # 이걸 for 문 밖에 두었었습니다.

import sys
from collections import deque, defaultdict

def bfs(start, plane_cnt) :
    q = deque()
    q.append(start)
    visit[start] =  1
    while q :
        if sum(visit) == N : 
            return plane_cnt
        now = q.popleft()
        for next in relation[now] :
            if visit[next] == 0 :
                q.append(next) # 큐에 넣는다는 것
                plane_cnt+=1 # 비행기에 탄다는 것
                visit[next] = 1 # 그 국가는 방문한다는 것

# 큐에 넣을 때!! 방문처리도 하고, 비행기를 하나 더 쓴다는 것이라서 비행기 +1
T = int(sys.stdin.readline().rstrip())
relation = defaultdict(list)
for _ in range(T) :
    # 비행기의 종류 M
    N,M = map(int, sys.stdin.readline().rstrip().split())
    for i in range(M) : 
        a,b = map(int, sys.stdin.readline().rstrip().split())
        relation[a].append(b)
        relation[b].append(a)
    # 국가의 수 N(2 ≤ N ≤ 1 000)
    visit = [ 0 for _ in range(1001) ]
    # 1번 국가부터 
    print(bfs(1,0))

<반성 점>

• mst에 대한 개념을 조금 복습안했다고 완전 까먹어 버렸습니다.
• mst의 가장 기초적인 지식에 대해서 꼼꼼히 알지 못했습니다.

<배운 점>

• 최소 신장트리의 복습
• 노드와 간선의 관계 (N - N-1)