[백준] 1260번 DFS와 BFS _ python

문제 : https://www.acmicpc.net/problem/1260

많은 시행착오 끝에 성공했지만, 상당히 비효율적인 내 코드는 다음과 같다.

통과한 내 코드

from collections import deque
import sys
sys.setrecursionlimit(99999)
def dfs(edge_stack, start):
    if start not in visit_node:
        visit_node.append(start)

        temp_lst = []
        for edge in input_lst:
            if start in edge:
                if edge[0] == start:
                    temp_lst.append(edge[1])
                else:
                    temp_lst.append(edge[0])
        temp_lst.sort(reverse=True)
        edge_stack.extend(temp_lst)

    if not edge_stack:
        return
    if len(visit_node) != n:
        start = edge_stack.pop()
        dfs(edge_stack, start)
    else:
        return

def bfs():
    edge_queue = deque()
    start = v
    while len(visit_node) != n:
        if start not in visit_node:
            visit_node.append(start)

            temp_lst = []
            for edge in input_lst:
                if start in edge:
                    if edge[0] == start:
                        temp_lst.append(edge[1])
                    else:
                        temp_lst.append(edge[0])
            temp_lst.sort()
            edge_queue.extend(temp_lst)
        if edge_queue:
            start = edge_queue.popleft()
        else:
            break

n, m, v = map(int, input().split())
input_lst = []
for _ in range(m):
    edge = list(map(int, input().split()))
    input_lst.append(edge)

edge_stack = []
visit_node = []

dfs(edge_stack, v)
print(*visit_node)

visit_node = []
bfs()
print(*visit_node)

1차 시도 실패

5% 쯤에서 런타임에러로 실패.
dfs에서 시작 노드에서 연결된 간선이 없는 경우 예외 처리를 해주지 않아서 발생

if not edge_stack:
	return

이 부분을 먼저 앞으로 빼서 처리해줘서 해결

2차 시도 실패

11% 쯤에서 런타임에러로 실패.
알고리즘 문제 그 동안 안 푼거 티나게 어이없는 실수를 했다. 이거 찾느라 2시간 썼다...

import sys
sys.setrecursionlimit(10000) # 또는 10 ** 6

나는 dfs를 구현할 때 재귀를 사용했고, 파이썬의 기본 재귀 깊이 제한은 1000으로 굉장히 적다.
따라서 위 코드를 통해서 재귀함수 제한을 반드시 크게 잡아야한다.

일단 통과는 했지만 다른 분들의 풀이와 비교해 봤을 때 시간복잡도가 매우 비효율적이다.

다른 분 풀이 참고

import sys
from collections import deque
input = sys.stdin.readline

### 2. DFS 구현
def DFS(graph, v):
    visited = {}
    stack = [v]
    while stack:
        d = stack.pop()
        if d not in visited:
            visited.setdefault(d)	# setdefault(d) key가 d인 value들에서 key와 value 하나를 인자로 받는 메소드
            stack += reversed(graph[d])
    return visited

### 3. BFS 구현
def BFS(graph, v):
    visited = {}
    deq = deque([v])
    while deq:
        d = deq.popleft()
        if d not in visited:
            visited.setdefault(d)
            deq += graph[d]
    return visited

### 1. dictionary로 그래프 구현
n, m, v = map(int, input().split())
graph = {i:[] for i in range(1,n+1)}

for i in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

for key in graph:
    graph[key].sort()

print(*DFS(graph, v))
print(*BFS(graph, v))

1. dictionary로 그래프 구현
미리 간선들을 dictionary로 찾기 편하게 구현해놓고 시작한다.
그리고 노드에 저장된 연결 노드들을 오름차순으로 정렬한다.
이 때 모든 노드에 대해 리스트를 초기화하고 그래프를 만들어야 시작 노드의 간선이 없는 경우를 고려할 수 있다.

2. DFS 구현
stack 내에 노드가 있다면 계속 반복되도록 while문으로 구현했다. 오름차순으로 노드를 방문해야하기 때문에 새로 스택에 추가되는 노드들은 reverse해서 삽입했다. 이 때 +=를 이용해 list 형태가 아니라 원소 하나씩 list에 추가될 수 있도록 했다. extend() 함수를 사용해도 된다.

3. BFS 구현
bfs는 내 코드와 마찬가지로 queue와 while문을 사용했다. 다만 나는 dfs와 bfs에서 모두 스택과 큐가 빈 경우와 방문한 노드 list의 길이가 전체 노드 수와 같은지를 모두 고려해서 종료시켰는데 사실 그럴 필요가 없다. 이 코드에서처럼 스택과 큐가 빈 경우만 고려해도 된다.

참고 : https://amber-chaeeunk.tistory.com/44 [채채씨의 학습 기록:티스토리]