11724 문제 질문
안녕하세요. 공부하다가 또 질문이 생겨 다시 한 번 질문 드립니다...리스트를 조회하는 것보다 딕셔너리를 조회하는 것이 더 빠를 거 같아서 문제의 그래프를 딕셔너리 자료형으로 바꿔주고 있는데요.제가 작성한 코드가 로컬에서 예시를 넣었을 때는 잘 되는데 백준에서는 틀린 답이라고 나옵니다..코드를 첨부하여 질문 드리고 싶은데, 멘토링 부분이 어디있는지 알려주시면 감사하겠습니다!
답변 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)1
kyg8821님 안녕하세요!
dictionary를 쓰려는 접근은 좋았는데 구현할 때 살짝 실수가 있었던 것 같아요.
main함수에서 dfs를 호출해주는 부분에서 1부터 N까지 포함하여 모든 노드를 확인해야 하는데 지금은 딕셔너리에 있는 노드들만 확인하고 있습니다.
딕셔너리에 있는 노드라는 건 다른 노드와 한번 이상 연결되어있는 노드이기 때문에, 혼자 동 떨어져있는 노드의 경우는 계산되지 않아 오답이 나오는 것 같고요!
그래서 for node in list(dic.keys()):
위 부분을
for i in range(1,N+1): 로 바꾸면 정답이 잘 나올것 같습니다 :)
0
여기에 코드 올려주셔도 봐드려요 🙂 올려주세요!
1
네 u,v 가 다르다는 건 서로 다른 두개의 노드가 연결되었다 (다른 말로 1, 1 혹은 2, 2 와 같이 한 노드가 자기 자신과 연결될 수는 없다)는 의미이지, 모든 노드가 포함된다는 의미는 아닙니다. 그래서 1부터 N+1까지 모두 확인이 필요합니다!
itertools, sys같은 STL을 사용할 수 없는 경우 질문드립니다.(백준 11724)
1
32
1
백준 13565 침투 질문
1
92
2
침투/섬개수 질문
1
138
2
재귀함수 질문
1
144
1
백준 1260 (DFS 와 BFS) 프린트 위치 질문
1
122
1
촌수계산(백준 2644) 질문
1
186
2
다른 주제 강의
1
137
2
graph
1
197
1
재귀 함수 Depth
1
181
1
백준 DFS
1
217
1
[바닥장식][런타임에러] 질문 있습니다.
1
292
3
그래프 짤 때 adjacency matrix vs adjacency list
1
393
2
2644문제(촌수 구하기) 질문입니다.
1
251
2
DFS 문제 하나 여쭤봅니다!..
1
297
1
다음강의
1
245
1
알고리즘 수업 - 깊이 우선 탐색 2( 백준 24480) 번 질문
1
285
1
1260 문제 풀이에서는 함수 global로 변수 선언
2
212
1
PyPy3와 Python3
1
332
1
백준 2606
1
216
1
22479번 문제 런타임 에러 도와주세요 ㅠㅠ
1
439
1
그래프 초기화
1
282
1
선생님! 바이러스 문제 코드 질문있어요오
1
276
2
질문있습니다!
1
332
1
2644 촌수계산 문제에 관한 질문
1
238
1