글 읽기 - [DFS와 BFS] 반례좀 부탁드려도 될까요?

ssw3095 4년 전 1

게시판의 다양한 반례들을 시도해 보았지만 아직 제 상황에 대한 반례를 찾지는 못했습니다..ㅠㅠ
혹시 지나가시다가 '저거 되나?'와 같은 사소한 문제가 보이면 살짝 피드백 혹은 반례를 좀 부탁드리겠습니다!

import sys
from collections import deque
sys.setrecursionlimit(10**6)


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

list_graph = [set([]) for _ in range(N+1)] # 인접 리스트를 구현합니다.
for _ in range(M):
    i, j = map(int, input().split())
    list_graph[i].add(j)
    list_graph[j].add(i)


list_print_d = [V] # 탐색한 순서를 저장하는 리스트 입니다.
list_visit_d = [0]*(N+1) # 방문을 체크하는 리스트 입니다.
list_visit_d[V] = 1 # 시작지점은 방문체크 해 줍니다.
def dfs(root):
    global list_graph, list_print_d
    for num in list_graph[root]: # root에 연결되어 있는 노드를 차례대로 탐색합니다.
        if not list_visit_d[num]: # 만약에 탐색이 안된곳이면
            list_visit_d[num] = 1 # 방문처리를 해 주고
            list_print_d.append(num) # 탐색했던 순서를 저장하는 리스트에 추가해 줍니다.
            dfs(num) # 그리고 현재 노드에서 다시 dfs() 함수를 실행시킵니다.


list_print_b = [] # 탐색한 순서를 저장하는 리스트 입니다.
list_visit_b = [0]*(N+1) # 방문을 체크하는 리스트 입니다.
list_visit_b[V] = 1 # 시작지점은 방문체크 해 줍니다.
def bfs(root):
    global list_graph
    list_queue = deque([root]) # bfs는 큐를 이용해 구현했습니다.
    #list_queue.append(root)
    while list_queue:
        num = list_queue.popleft() # 큐에 있는 값을 pop해주고
        list_print_b.append(num) # 방문 순서를 기록하는 리스트에 추가합니다.
        for i in list_graph[num]: # 그리고 현재 노드에 연결된 노드들을 탐색합니다.
            if not list_visit_b[i]: # 만약 방문하지 않았다면
                list_visit_b[i] = 1 # 방문체크를 해주고
                list_queue.append(i) # 현재노드를 큐에 push해줍니다.

dfs(V)
bfs(V)
print(*list_print_d)
print(*list_print_b)

hello708250 4년 전 1

set은 해시를 이용해서 값을 집어넣기 때문에 set을 이용하면 무조건 정렬이 된다고 볼 수가 없습니다.

https://stackoverflow.com/questions/15479928/why-is-the-order-in-dictionaries-and-sets-arbitrary/26099671#26099671

input:
9 1
2
3
4
5
7
8
6
9
9

answer:
2 4 5 6 9 7 3 8
2 3 4 5 7 8 6 9



print(set([1,3,7,8,11,21,33,37,55,88]))
=>{1, 33, 3, 37, 7, 8, 11, 21, 55, 88}

ssw3095 4년 전 0

그렇군요..!

set을 사용한 것이 문제일거라고는 상상도 못했네요..ㅠㅠ

덕분에 솔팅함수를 구현후 적용해보니 정답처리가 되었네요!

감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[DFS와 BFS] 반례좀 부탁드려도 될까요?

ssw3095 4년 전 1

hello708250 4년 전 1

ssw3095 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말