[ BOJ ] 1260 DFS와 BFS - python 문제풀이

1260 DFS와 BFS

접근 : 기본 DFS, BFS 구현 문제라 별다른 전략은 세우지 않았고, 다양한 방법으로 풀어보려 했다

풀이 방법
1. 함수X while문으로 stack 활용해서 풀기
2. dfs는 함수 활용, bfs는 deque 활용하기

 

방법1. 함수 없이 while문 활용해서 푼 방법

N,M,V = map(int, input().split())
# 정점 i를 key, i와 연결된 정점들을 리스트에 담아 value로 갖는 딕셔너리 info 
info = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int, input().split())
    info[a].append(b)
    info[b].append(a)

# 문제 조건 : 정점이 작은 순서대로 방문
for i in range(1,N+1):
    info[i].sort()

# 이미 지나간 정점인지 확인하기 위한 배열
v_dfs = [0]*N
v_bfs = [0]*N

# 결과를 담을 배열
r_dfs = []
r_bfs = []

s = [V]
while s:
	# bfs는 앞에서부터 꺼내기
    n = s.pop(0) 
    if v_bfs[n-1] == 0:
        v_bfs[n-1] = 1
        r_bfs.append(n)
        for j in range(len(info[n])):
            if v_bfs[info[n][j]-1] == 0:
                s.append(info[n][j])

# 문제 조건 - 스택은 뒤에서부터 꺼내기 때문에 역순 정렬해야 작은 값이 나중에 스택에 들어감
for i in range(1,N+1):
    info[i].sort(reverse=True)

s = [V]
while s:
    n = s.pop()
    if n not in r_dfs:
        r_dfs.append(n)
    v_dfs[n-1] = 1
    for j in range(len(info[n])):
        if v_dfs[info[n][j]-1] == 0:
            s.append(info[n][j])

print(" ".join(map(str, r_dfs)))
print(" ".join(map(str, r_bfs)))

29964KB, 524ms

 

방법2. dfs는 함수 활용, bfs는 deque 활용하기

def dfs(x,li):
    li.append(x)
    for i in range(len(info[x])):
        if info[x][i] not in li:
            li = dfs(info[x][i],li)
    return li

N,M,V = map(int, input().split())
info = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int, input().split())
    info[a].append(b)
    info[b].append(a)

for i in range(1,N+1):
    info[i].sort()

v_bfs = [0]*N

r_dfs = dfs(V,[])
r_bfs = []

from collections import deque
s = deque()
s.append(V)
while s:
    n = s.popleft()
    if v_bfs[n-1] == 0:
        v_bfs[n-1] = 1
        r_bfs.append(n)
        for j in range(len(info[n])):
            if v_bfs[info[n][j]-1] == 0:
                s.append(info[n][j])

print(" ".join(map(str, r_dfs)))
print(" ".join(map(str, r_bfs)))

33832KB, 632ms