글 읽기 - 게시판 글 전부 읽어보고 테스트도 다 돌려봤는데 에러가 뜹니다..

ringo90h 4년 전 0

하루종일 테스트만 돌려보고 게시글도 다 참고해서 에러 해결했는데 런타임 에러가 뜨네요..

재귀도 안썼는데 왜이런걸꺼요 ㅠㅠ

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

#인접리스트 생성
for i in range(M):
    p = input().split()
    if p[0] not in g:
        g[p[0]] = set()
    if p[1] not in g:
        g[p[1]] = set()
    g[p[0]].add(p[1])
    g[p[1]].add(p[0])

def dfs(g, start):
    visited = set()
    visitStack = [start]
    result = []
    while visitStack:
        n = visitStack.pop()
        if n not in visited:
           visited.add(n)
           result.append(n)
           gCheck = g[n]-visited
           gSort = sorted(list(gCheck), reverse=True, key=int)
           visitStack += gSort
    return result


def bfs(g, start):
    visited = set()
    visitQueue = [start]
    result = []
    while visitQueue:
        n = visitQueue.pop(0)
        if n not in visited:
            visited.add(n)
            result.append(n)
            gCheck = g[n]-visited
            gSort = sorted(list(gCheck),key=int)
            visitQueue += gSort
    return result

print(*dfs(g, str(V)))
print(*bfs(g, str(V)))

pichulia 4년 전 0

visited하지 않은 애들을 전부 visitStack에다가 집어넣고 계신데...

예를 들어 선형으로 연결된 그래프(1~2-3-...-N)가 있고

모든 노드가 다 N이랑 연결되있으면

N은 아직 방문된 적이 없으니 visitStack에 계속해서 쌓여만가고

결곡 한 N만 N-1개 있을겁니다.

이게 N만 그런게 아니라 N-1, N-2같은 애들한테도 똑같은 상황이 발생해서

결국 visitStack에는 중복되는 값이 넘처흐르게 되는 상황이 오는거죠.

차라리 재귀로 짜시는게..

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

문제

문제

출처

ICPC

게시판 글 전부 읽어보고 테스트도 다 돌려봤는데 에러가 뜹니다..

ringo90h 4년 전 0

pichulia 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말