2023.01.19 연결요소의 개수 백준[파이썬]

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

11724번: 연결 요소의 개수

import sys
from collections import defaultdict

input = sys.stdin.readline

def find_area(n):
    check = [0] * (n+1)
    answer = n
    for i in graph:
        if check[i-1] != 0:
            continue
        visited = []
        discovered = [i]
        while discovered:
            pos = discovered.pop()
            visited.append(pos)
            for j in graph[pos]:
                if j in discovered or j in visited:
                    continue
                discovered.append(j)
                check[j-1] = 1
                answer -= 1
    return answer

n,m = map(int, input().split())
graph = defaultdict(list)
for _ in range(m):
    i , j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)
print(find_area(n))

문제를 푸는데 순간 뇌가 굳어서 이상한 코드가 나왔다.. 아이디어가 문제를 풀다가 떠올라서 일단 진행을 했다.

dfs로 하면서 check로 확인하면서 dfs를 넣었으면 됐을거 같은데 전체적인 구조는 비슷하지만 다음에 깔끔하게 다시 짜 봐야겠다. 문제자체는 dfs 돌면서 갔던곳은 안 갈 때 새로운 곳을 갈 때마다 이어져 있는 거라고 생각해서 전체 n 에서 1씩 빼는 식으로 진행 했다. 만약 정점의 개수가 [1,2,3,4] 4개이고 1이 모든 곳을 다 간다면 4(전체 정점의 개수) - 3(새롭게 간 곳)을 해서 답이 1이 나온다.