[백준] 11724번 파이썬 - DFS 풀이

문제 요약 (11724. 연결 요소의 개수)

방향이 없는 그래프(양방향 그래프)의 노드와 간선이 주어졌을 때 연결 요소의 개수를 구하는 것이다.

연결 요소는 연결된 노드들의 뭉텅이라고 생각하면 문제를 풀기 편하다.
ex. 1-5-2, 3-4, 6 이렇게 연결되어 있다면 연결 요소의 개수는 3이다.

 

11724번: 연결 요소의 개수

 

풀이를 위한 부연 설명

• 입력되는 값들을 받아 그래프를 완성한다.
• 그래프 내에서 연결 요소를 찾아야하므로 BFS 보다는 DFS를 써야 답을 구할 수 있다.
  • 따로 stack을 만들고 탐색해야하는 노드들을 넣어둔다.
  • DFS를 사용해야하기 때문에 해당 노드를 모두 탐색하였는지 확인할 수 있는 bool 타입의 리스트가 필요하다
• 문제에서 1부터 노드의 값이 주어진다.
  • 그래프 내 노드를 위한 리스트 개수를 정확하게 주어지는 정점의 개수만큼만 만들어도 된다.
  • 그러나 편하게 인덱스 값에 접근하기 위해 0번 인덱스에는 빈 값을 넣고 리스트를 하나 더 만들어 두면 좋다.
  • 따로 인덱스 값 -1을 할 필요가 없다.
• DFS를 재귀적 함수 형태로 풀어도 된다.

• DFS에 대한 개념과 연관 문제는 다음 게시글을 참고하면 된다.

[코테 알고리즘] DFS, BFS / 관련 문제

 

코드

import sys
input = sys.stdin.readline

node, edge = map(int, input().split())
# 그래프
graph = [[] for _ in range(node+1)]
# 방문 여부 표시를 위한 리스트
visited = [False] * (node + 1)

for i in range(edge):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

stack = []

# DFS 탐색을 위한 함수
def dfs(new):
    while stack:
        n = stack.pop()
        if not visited[n]:
            for i in graph[n]:
                stack.append(i)
            visited[n] = True

cnt = 0

for test in range(1, node+1):
    if not visited[test]:
        stack.append(test)
        dfs(test)
        # 만약 이전에 방문했다면 하나의 연결 노드였을 것이다.
        cnt += 1

print(cnt)

 

기억할 점

• DFS는 재귀함수를 사용하지 않아도 해결 할 수 있다.
• DFS는 해당 노드를 방문해서 모든 가지를 확인했는지 검사하는 것이 반드시 필요하다. 따로 배열을 만들어주자
• 새로운 연결 요소인지 확인하는 로직을 짜는데 굉장히 시간이 오래 걸렸다.