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

🥚문제

---

🥚입력/출력

---

🍳코드

from sys import stdin
from collections import deque
input = stdin.readline

n, m = map(int, input().split())

# 그래프 생성
graph = [[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u][v] = graph[v][u] = 1

# 방문 여부를 표시하는 visited
visited = [False]*(n+1)
# 요소의 개수를 표시하는 component
component = 0

# bfs 함수
def bfs(x):
    # 전역 변수 선언
    global component

    q = deque()
    q.append(x)
    visited[x] = True
    while q:
        u = q.popleft()
        # 연결된 정점을 탐색한다
        for v in range(1, n+1):
            if graph[u][v] == 1 and not visited[v]:
                q.append(v)
                visited[v] = True
    # q가 비었을 때
    component += 1

# bfs 알고리즘
for i in range(1, n+1):
    if 1 in graph[i] and not visited[i]:
        bfs(i)

# 간선이 없는 노드들도 챙겨주자!
# visited에 표시된 True가 n(노드의 개수)보다 작다면
if visited.count(True) < n:
    # visited에 표시되지 않은, 간선이 없는 노드들의 개수를 component에 더함
    component += n-visited.count(True)

# 출력
print(component)

---

🧂아이디어

• 예전에 한창 BFS DFS 풀고 있었을 때 풀었다가 실패했었나보다
• 오늘은 2트만에 성공했다!
• 생각지 못한 케이스가 있었는데 (특이하다거나 기발한 케이스는 아니었고 내가 꼼꼼하지 못해서 넘어간 케이스), 간선이 없는 Node들도 component 하나하나로 카운트해줘야 한다는 것이다! 이건 나중에 비슷한 문제에서도 늘 유념해야 할 것 같다❗❗