[백준] 11724 연결 요소의 개수 (실버2) / DFS

문제요약

그림과 같이 되어있다면 연결된 요소로 친다.

나의 코드 및 설명

• 이차원 리스트에 그래프 정보를 저장한다.
• dfs 함수 : 시작노드를 의미하는 변수 sn과 연결된 노드들의 방문 정보를 체크한다. 만약 방문하지 않은 노드라면 방문 체크하고, 해당 노드에 대한 하위 dfs 함수를 호출한다.
• 메인 함수에서 1번 노드부터 마지막 노드까지 방문하며 아직 방문하지 않은 노드가 있다면 dfs 함수를 호출하고 카운트한다.

import sys
sys.setrecursionlimit(10**4)

def dfs(sn):
    for i in board[sn]:
        if visited[i] == 0:
            visited[i] = sn
            dfs(i)

n,m = map(int, input().split())
board = [[] for _ in range(n+1)]
visited = [0] * (n+1)
for _ in range(m):
    start, end = map(int ,input().split())
    board[start].append(end)
    board[end].append(start)

count = 0

#1번노드부터 마지막 노드까지 방문
for i in range(1,n+1):
    #만약 해당 노드가 방문 전이라면
    if visited[i] == 0:
        #방문해서 dfs수행
        #노드가 연결되어 있다면 연결된 노드의 방문 테이블은 갱신될 것
        dfs(i)
        count += 1

print(count)

피드백

DFS 연습을 위해 풀어본 문제. 이 문제는 Pypy로 실행시켜 통과할 수 있었는데, 파이썬으로 실행시켜 통과하기 위해서는 input() 대신 sys.stdin.readline() 을 사용하면 통과할 수 있다고 한다. 코드에는 별 문제가 없이 정상적으로 구현한 것 같아 빠르게 다음 문제로 넘어가도록 하자.