인프런 커뮤니티 질문&답변

작성한 질문수

[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편

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

11724 문제 질문

해결된 질문

작성

·

220

1

안녕하세요. 공부하다가 또 질문이 생겨 다시 한 번 질문 드립니다...리스트를 조회하는 것보다 딕셔너리를 조회하는 것이 더 빠를 거 같아서 문제의 그래프를 딕셔너리 자료형으로 바꿔주고 있는데요.제가 작성한 코드가 로컬에서 예시를 넣었을 때는 잘 되는데 백준에서는 틀린 답이라고 나옵니다..코드를 첨부하여 질문 드리고 싶은데, 멘토링 부분이 어디있는지 알려주시면 감사하겠습니다!

python 코딩-테스트 알고리즘 dfs python3

답변 2

1

질문자

import sys
import collections
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, M = map(int, input().split())

dic = collections.defaultdict(list)
visited = []
result = 0

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


def dfs(node):
    global visited, dic
    visited.append(node)

    for n in dic[node]:
        if n not in visited:
            dfs(n)


for node in list(dic.keys()):
    if node not in visited:
        dfs(node)
        result += 1

print(result)

질문자

제가 작성한 코드에요!

개발자로 취직하기

지식공유자

kyg8821님 안녕하세요!

dictionary를 쓰려는 접근은 좋았는데 구현할 때 살짝 실수가 있었던 것 같아요.

main함수에서 dfs를 호출해주는 부분에서 1부터 N까지 포함하여 모든 노드를 확인해야 하는데 지금은 딕셔너리에 있는 노드들만 확인하고 있습니다.

딕셔너리에 있는 노드라는 건 다른 노드와 한번 이상 연결되어있는 노드이기 때문에, 혼자 동 떨어져있는 노드의 경우는 계산되지 않아 오답이 나오는 것 같고요!

그래서 for node in list(dic.keys()):

위 부분을

for i in range(1,N+1): 로 바꾸면 정답이 잘 나올것 같습니다 :)

0

개발자로 취직하기

지식공유자

여기에 코드 올려주셔도 봐드려요 🙂 올려주세요!

질문자

코드 올려드렸어요!

질문자

근데 문제를 살펴보면 u와 v가 같지 않아야한다는 조건이 있어서, 혼자 동 떨어져있는 노드의 경우가 발생할 수 있는지 의문이 생깁니다..

개발자로 취직하기

지식공유자

네 u,v 가 다르다는 건 서로 다른 두개의 노드가 연결되었다 (다른 말로 1, 1 혹은 2, 2 와 같이 한 노드가 자기 자신과 연결될 수는 없다)는 의미이지, 모든 노드가 포함된다는 의미는 아닙니다. 그래서 1부터 N+1까지 모두 확인이 필요합니다!

질문자

아!! 이해했습니다! 설명 너무 감사드려요 ㅠㅠ

작성한 질문수