[Python][백준/BOJ] 9372번 : 상근이의 여행

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

9372번: 상근이의 여행

 

내 코드

import sys
input = sys.stdin.readline

t=int(input())
def dfs(a, cnt):
    visited[a]=1
    
    for i in graph[a]:
        if not visited[i]:
            cnt = dfs(i, cnt+1)
    return cnt
                
                
for _ in range(t):
    cnt =0
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    visited =[0]*(n+1)
    
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
   

    print(dfs(1, 0))

 

코드 리뷰

for _ in range(int(input())):
    cnt=0
    n, m = map(int, input().split())
    graph = [[0]*(n) for i in range(n+1)]
    visited =[0]*(n+1)

테스트 케이스 한 번 동안 모든 카운팅 변수들을 초기화해준다.

for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

그리고 한 번의 테스트 케이스 안에서 그래프 a에 b를 저장하고, b에 a를 저장해서 서로 연결되었음을 저장한다.

def dfs(a, cnt):
    visited[a] =1
    
    for i in graph[a]:
        if not visited[i]:
            cnt = dfs(i, cnt+1)
            
    return cnt

어차피 a에서 b를 발견하게 되면, b도 마찬가지로 a가 연결되어 있을 것이므로 앞의 변수인 a하나만 함수로 가져간다.

그리고 visited 를 통해 방문했음을 저장하고, 만약 graph[a] 에 있지만 아직 방문하지 않은 변수라면 i를 다시 a에 넣어서 반복한다.

이후 연결된 개수인 cnt만 +1씩 더해주고 저장해서 리턴하면 끝이다.

cnt = dfs(i, cnt+1)

특히 cnt는 지금 dfs()안에만 갇혀있고, 이 밖으로 나온 적이 없으므로 리턴할 때 리턴할 cnt가 뭐야? 할 수 있다.

리턴이 안 될 수 있으므로 cnt = dfs() 이렇게 적어주면 cnt를 밖으로 끄집어낼 수 있다.

 

신장트리(Spanning Tree)

해당 문제는 신장트리 개념을 잘 알고 있는지를 묻는 문제이다. 그래서 해결 방법중에 단순히 N-1 만 해서 답을 구할 수도 있다. 이 이유는 신장트리의 특성 때문인데, 연결 그래프의 모든 노드가 연결되어 있기 때문이다.

위와 같이 4개의 정점이 있을 때, 4개의 정점을 모두 연결한 3(n-1)개의 엣지로 이루어진 그래프는 모두 신장트리라고 할 수 있다.

그래서 신장트리는 DFS나 BFS로 탐색을 했을 때 경로 자체가 신장트리가 된다.

 

최소 비용 신장트리(MST - Minimum Cost Spanning Tree)

최소 비용 신장트리를 구할 수 있는 알고리즘은 다음과 같다.

• 크루스칼(Kruskal) 알고리즘
• 프림(Prim) 알고리즘
• 솔린(Sollin) 알고리즘

주로 모든 점들이 서로 연결되어 있지만, 연결된 길이를 최소로 할 때 많이 사용된다.

~ 가 모두 연결되어 있지만, 이 길이가 최소가 되게 하는 방법을 구하시오.