[백준][python] 1260 : DFS와 BFS

트러블슈팅

런타임에러(RecursionError)

dfs에서 재귀함수를 사용해 해당 에러가 발생했다. 파이썬의 경우 정해진 최대 재귀 깊이가 있기때문에

임포트밑에 코드를 추가해주어 해결하였다. (넉넉하게 10의 6승)

sys.setrecursionlimit(10**6)

https://help.acmicpc.net/judge/rte/RecursionError

런타임 에러 (RecursionError)

 

간선이 없는 정점이 있는 케이스

모든 정점의 간선에 빈리스트를 추가

반례

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

글 읽기 - DFS와 BFS, 20%에서 구현이 틀렸습니다.

 

전체코드

코드

import sys
from sys import stdin as s
from queue import Queue
sys.setrecursionlimit(10**6) #재귀 한계 해제
s = open("input.txt") #제출시에는 해당라인 주석처리
N, V, M = map(int, s.readline().split())

#간선 딕셔너리에 생성
edge = {}
for i in range(1,N+1): #간선이 없는 정점의 경우라도 빈리스트가 존재해야함
    edge[i] = []
for i in range(V):
    v1, v2 = map(int, s.readline().split())
    edge[v1].append(v2)
    edge[v2].append(v1)

#간선 정렬
for i in edge:
    edge[i].sort()

def dfs(now):
    visited.append(now)
    for v in edge[now]:
        if v not in visited:
            dfs(v)

def bfs(que):
    now = que.get()
    visited.append(now)
    for v in edge[now]:
        if v not in list(que.queue) and v not in visited:
            que.put(v)
    if que.empty():
        return
    bfs(que)

visited = []
dfs(M)
print(" ".join(str(i) for i in visited)) #join사용해서 리스트값을 이쁜 모양으로 출력
que = Queue()
que.put(M)
visited = []
bfs(que)
print(" ".join(str(i) for i in visited))

코드

import sys
from sys import stdin as s
from queue import Queue
sys.setrecursionlimit(10**6) #재귀 한계 해제
# s = open("input.txt") #제출시에는 해당라인 주석처리
N, V, M = map(int, s.readline().split())

#간선 딕셔너리에 생성
edge = {}
for i in range(1,N+1): #간선이 없는 정점의 경우라도 빈리스트가 존재해야함
    edge[i] = []
for i in range(V):
    v1, v2 = map(int, s.readline().split())
    edge[v1].append(v2)
    edge[v2].append(v1)

#간선 정렬
for i in edge:
    edge[i].sort()

def dfs(now):
    visited[now-1] = True
    result.append(now)
    for v in edge[now]:
        if visited[v-1] is False:
            dfs(v)

def bfs(que):
    now = que.get()
    visited[now-1] = True
    result.append(now)
    for v in edge[now]:
        if v not in list(que.queue) and visited[v-1] is False:
            que.put(v)
    if que.empty():
        return
    bfs(que)

visited = [False]*N
result = []
dfs(M)
print(" ".join(str(i) for i in result)) #join사용해서 리스트값을 이쁜 모양으로 출력
que = Queue()
que.put(M)
visited = [False]*N
result = []
bfs(que)
print(" ".join(str(i) for i in result))

visited를 true or false 리스트로 변경