(DFS) 백준 11724번 연결 요소의 개수

import sys

input = sys.stdin.readline

N, M = map(int, input().split(" "))
dfs_list = [[0 for i in range(N+1)] for k in range(N+1)]

for _ in range(M):
    x, y = map(int, input().split(" ")) # 그래프를 탐색하기 위해 연결되어 있는 요소를 1로 만들어준다.
    dfs_list[x][y] = 1
    dfs_list[y][x] = 1

visited = [False] * (N+1) # 방문을 체크하기 위해 visited를 N+1 만큼(1부터이므로) False로 초기화 해준다.
count = 0

def solution(v):

    if visited[v] == True: # 이미 방문했으면 False 리턴하고 종료
        return False

    visited[v] = True # 방문한 점은 방문체크를 해준다.
    for i in range(1, N+1):
        if dfs_list[v][i] == 1: # 만약에 연결되어 있으면 계속 탐색
            solution(i)

    return 1

for i in range(1,N+1):
    response = solution(i)

    if response == 1: # 1을 반환할 경우 count 1증가.
        count += 1

print(count)

한번 풀었던 문제이다.

처음에 아래와 같이만 조건을 주었는데

dfs_list[x][y] = 1

실패했다. 곰곰이 생각해보니 연결 지점이 나중에 나타나는 경우 오류가 발생하기 때문이다.

ex) 만약에
1 2
2 5
5 3
6 4
같은 경우에 1부터 시작해서 각 지점을 방문 처리 하는데 4같은 경우에는 1로 표시된 지점이 없기 때문에 지나가고 방문 처리되고 1을 반환해버린다. 그리고 마지막 6 4에 가서 6도 방문처리가 되고 1을 반환해서 문제가 생긴다.
그래서

dfs_list[x][y] = 1
dfs_list[y][x] = 1

위와 같이 처리를 해주어야 한다.