백준 1260 DFS 와 BFS Python 실버 2

틀린 코드 5% 

1. 인접리스트를 만들었었음 = 오름차순 정리를 위해 반복문 + 리스트를 반복해서 사용함 => 시간낭비

=> 인접행렬로 변경해서 해결

2. 예제 케이스는 다 맞았었음 하지만 dfs코드가 불안정했음

=> 바꿨음에도 문제 발생

def dfs(v):
    visited_d[v] = 1
    path.append(v)
    for i in adjl[v]:
        if visited_d[i]: continue
        dfs(i)

 

# 1260 DFS 와 BFS 실버2
from collections import deque
def dfs(v):
    if len(path) == m+1:
        return
    for i in adjl[v]:
        if visited_d[i]: continue
        visited_d[i] = 1
        path.append(i)
        dfs(i)
def bfs(v):
    visited_b = [0] * (n + 1)
    deq = deque()
    deq.append(v)
    visited_b[v] = 1
    path_b = []
    while deq:
        value = deq.popleft()
        path_b.append(value)
        for i in adjl[value]:
            if visited_b[i]: continue
            visited_b[i] = 1
            deq.append(i)
    return path_b
n, m, v = map(int,input().split())
arr = []
adjl = [[] for _ in range(n+1)]
for i in range(m):
    s,e = map(int,input().split())
    arr.append((s,e))

arr.sort()
for i in range(m):
    s,e = arr[i]
    adjl[s].append(e)
    adjl[e].append(s)
path = [v]
visited_d = [0] * (n+1)
visited_d[v] = 1
dfs(v)
print(*path)
print(*bfs(v))

정답 코드:

# 1260 DFS 와 BFS 실버2
from collections import deque
def dfs(v):
    visited_d[v] = 1
    path.append(v)
    for i in range(1,n+1):
        if not visited_d[i] and adjl[v][i]:
            dfs(i)
def bfs(v):
    visited_b = [0] * (n + 1)
    deq = deque()
    deq.append(v)
    visited_b[v] = 1
    path_b = []
    while deq:
        value = deq.popleft()
        path_b.append(value)
        for i in range(1,n+1):
            if not visited_b[i] and adjl[value][i]:
                visited_b[i] = 1
                deq.append(i)
    return path_b
n, m, v = map(int,input().split())
adjl = [[False] *(n+1) for _ in range(n+1)]
for i in range(m):
    s,e = map(int,input().split())
    adjl[s][e] = True
    adjl[e][s] = True
path = []
visited_d = [0] * (n+1)
dfs(v)
print(*path)
print(*bfs(v))