[백준 / Python] 연결 요소의 개수_11724

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

 

 

정답 풀이

 

dfs로 풀었다.

n, m = map(int, input().split())
data = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    data[a].append(b)
    data[b].append(a)
visited = [False for _ in range(n + 1)]


def dfs(idx):
    for i in data[idx]:
        if not visited[i]:
            visited[i] = True
            dfs(i)


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

 

 

 

 

궁금한 풀이

from _collections import deque

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

data = [[] for _ in range(n + 1)]

for _ in range(m):
    x, y = map(int, input().split())
    data[x].append(y)
    data[y].append(x)

q = deque()
visited = [False for _ in range(n + 1)]

result = 0
for i in range(1, n + 1):
    if visited[i] == False:
        q.append(i)
        visited[i] = True
        result += 1
        while q:
            index = q.popleft()

            for node in data[index]:
                if visited[node] == False:
                    visited[node] = True
                    q.append(node)

print(result)

 

Q1. 왜 data[b].append(a)를 뺴주면 답이 틀리게 나올까?

아,, data는 그래프를 표현한 것이다.

문제에서 주어진 그래프는 "양방향" 그래프이다. 하지만 한쪽으로 간선만 넣어주면 그것은 양방향 그래프가 아니다.

예를 들어, (1, 2). (2, 5). (5, 1)가 주어졌다고 가정해보자.

단방향으로 만들면 어떻게 되겠는가?

두 개가 연결이 되어있어도, 한쪽으로만 연결이 되어있기 때문에 문제에서 제시해주는 내용과 전혀 다르게 흘러간다.

결론: 양방향 그래프이기 때문이다.