[Python][백준/BOJ] 11724번 : 연결 요소의 개수

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

11724번: 연결 요소의 개수

 

내 코드

import sys
input = sys.stdin.readline

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

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

cnt =0
def dfs(i):
    stack=[]
    stack.append(i)
    visited[i] =True
    while stack:
        now = stack.pop()
        for nxt in graph[now]:
            if not visited[nxt]:
                stack.append(nxt)
                dfs(nxt)

for i in range(1, n+1):
    if not visited[i]:
        cnt+=1
        dfs(i)
print(cnt)

 

DFS

전형적인 DFS 문제 중 하나였다.

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

우선 연결되어 있는 수를 모두 저장해주는데, 연결되어 있는 각 정점들이 나올 경우에는 이렇게 저장하는 것이 편한 것 같다. 이러면 나름 나중에 FOR문에서 불러오기가 편하다.

 

def dfs(i):
    stack=[]
    stack.append(i)
    visited[i] =True
    while stack:
        now = stack.pop()
        for nxt in graph[now]:
            if not visited[nxt]:
                stack.append(nxt)
                dfs(nxt)

DFS 함수이다. 풀고 나서 사람들의 코드를 봤더니, DFS 함수가 매우 단순했다. 나의 코드만 이렇게 복잡했다.

stack을 하나 만들어주고, 방문하면 i를 방문하고, stack에 i를 추가해준다. 

그리고 stack 에 수가 있는 동안에는 수를 빼주고, graph[i]에 해당 수가 있고 아직 방문하지 않은 상태인지 확인한다.

조건을 모두 부합한다면 stack 에 수를 넣고, dfs 로 돌린다.

 

for i in range(1, n+1):
    if not visited[i]:
        cnt+=1
        dfs(i)

그리고 해당 문제는 n개의 정점에서 연결된 개수가 총 몇개인지를 묻고 있다. 이를 알아내기 위해 1부터 n까지 모두 다 체크한다.

하지만 이미 연결한 걸 체크해버린 수가 등장하면 중복 체크가 되어 오답처리가 되니까, 방문하지 않은 것만을 대상으로 dfs 안에 넣고 돌려야 한다.

여기서 발견한 수는 start점이 된다. 그래서 dfs 함수 한바퀴 시원하게 돌고 cnt+1이 되는 것이다.