글 읽기 - 파이썬 출력초과 반례

dev_rookie37 2년 전 0

다른 글의 반례를 입력해도 문제가 없는데..

출력 초과가 계속 뜹니다.

물론 다르게 코드를 작성할 수는 있겠지만, 제 코드의 어느 부분이 문제인지 알고싶습니다.

감사합니다!

from sys import stdin
from collections import deque, defaultdict

input = stdin.readline


def dfs(graph, s):
    visit = {}
    for key in graph.keys():
        visit[key] = False

    stack = [s]
    #while False in visit.values(): 수정
    while stack:
        p = stack.pop()
        visit[p] = True
        print(p, end=' ')
        for c in reversed(graph[p]):
            if visit[c]:
                continue
            if c not in stack: # 추가한 조건
                stack.append(c)


def bfs(graph, s):
    visit = {}
    for key in graph.keys():
        visit[key] = False

    queue = deque([s])
    #while False in visit.values(): 수정
    while queue:        
        p = queue.popleft()
        visit[p] = True
        print(p, end=' ')
        for c in graph[p]:
            if visit[c]:
                continue
            if c not in queue: # 추가한 조건
                queue.append(c)
            

def duplicate(t):
    return (t[1], t[0])


if __name__ == '__main__':
    N, M, V = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(M)]

    # bidirectional edges
    edges = edges + list(map(duplicate, edges))
    edges = list(set(edges))
    edges.sort()

    graph = defaultdict(list)
    for e in edges:
        if e[0] not in graph:
            graph[e[0]]
        graph[e[0]].append(e[1])

    dfs(graph, V)
    print()
    bfs(graph, V)

djm03178 2년 전 1

출력 초과는 아니지만 연관이 있는 반례 드립니다.

2 1
2
4

djm03178 2년 전 2

위에 건 직접적인 연관은 아니고 이게 좀 더 직접적인 연관이 있습니다.

dev_rookie37 2년 전 0

감사합니다. 끊어진 그래프와, 스택이나 큐에 이미 들어가있는 vertex를 확인하는 조건을 주지 않았었네요.

dev_rookie37 2년 전 0

말씀해주신 반례 처리하는 코드를 추가 및 수정했는데요, 여전히 출력 초과가 뜨네요 ㅠ 잘못처리되는 부분이 또 있을까요

djm03178 2년 전 0

일단 이 코드는 틀리게 출력되는 반례가 또 있습니다. 아래 케이스에서 DFS가 1 2 4 3 5를 출력해야 하지만 1 2 4 5 3가 출력됩니다.

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

문제

문제

출처

ICPC

파이썬 출력초과 반례

dev_rookie37 2년 전 0

djm03178 2년 전 1

djm03178 2년 전 2

dev_rookie37 2년 전 0

dev_rookie37 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말