글 읽기 - 반례를 못 찾겠습니다.

jihochoi 5년 전 0

stack 과 queue를 이용하여 iterative 하게 풀었습니다만 반례를 못 찾겠습니다.

# TODO Recursive Version
# BFS, DFS

# vertex, edge (node, link), start
N, M, V = map(int, input().split(" "))

links_dict = {new_set: set() for new_set in range(N + 1)}

for _ in range(M):
    a, b = map(int, input().split(" "))
    links_dict[a].add(b)
    links_dict[b].add(a)


# DFS - stack, iterative

def dfs(graph, start):
    visited = []  # foot_prints
    stack = [start]

    while stack:
        top = stack.pop()
        if top not in visited:
            visited.append(top)
            neighbors = list(graph[top])[::-1]
            for neighbor in neighbors:
                if neighbor not in visited:
                    stack.append(neighbor)
    return visited


# BFS - queue

def bfs(graph, start):
    visited = []  # foot_prints
    queue = [start]

    while queue:
        front = queue.pop(0)
        if front not in visited:
            visited.append(front)
            for neighbor in graph[front]:
                if neighbor not in visited:
                    queue.append(neighbor)

    return visited


for node in dfs(links_dict, V):
    print(node, end=" ")

print("")
for node in bfs(links_dict, V):
    print(node, end=" ")

ploffer11 5년 전 0

https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

반례를 못 찾겠습니다.

jihochoi 5년 전 0

ploffer11 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말