[백준] 1260 DFS와 BFS

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

# dfs(재귀), bfs(큐) 로 구현
n, m, r = map(int, input().split()) 
graph = [ [] for _ in range(n+1)]
visited_dfs = [0] * (n+1)
visited_bfs = [0] * (n+1)

ans_dfs = []
ans_bfs = []
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for lst in graph:
    lst.sort()

#dfs(재귀)
def dfs(graph, r, visited_dfs):
    ans_dfs.append(r)
    visited_dfs[r] = True
    for i in graph[r]:
        if visited_dfs[i] == 0:
            dfs(graph, i, visited_dfs)

#bfs(큐)
def bfs(graph, r, visited_bfs):
    queue = deque()
    # 시작 노드 큐에 삽입 & 방문 처리
    queue.append(r)
    visited_bfs[r] = True
    while queue:
        v = queue.popleft()
        ans_bfs.append(v)
        for i in graph[v]:
            if visited_bfs[i] == 0:
                queue.append(i)
                visited_bfs[i] = True
# 실행
dfs(graph, r, visited_dfs)
bfs(graph, r, visited_bfs)
# 결과 출력
for val in ans_dfs:
    print(val, end=' ')
print()
for val in ans_bfs:
    print(val, end=' ')

다시 풀기

1
파이썬의 변수 스코프와 for문 동작 방식에 대해 알게 되었다.
예제

v = 100
arr = [1, 2, 3, 4]

for v in arr:
    print(v)  # for문 안에서 v가 1, 2, 3, 4로 바뀜

print(v)  # 마지막 값 4가 저장됨

• for v in arr: 에서 v는 새로운 지역 변수가 아니라 기존의 전역 변수 v에 값을 덮어쓴다.
• 따라서 for 문이 끝난 뒤에도 마지막으로 할당된 값이 전역 변수에 남게 됨.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m, v = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

for arr in graph:
    arr.sort()

# dfs
ans = []
visited = [0] * (n+1)
def dfs_rec(graph, visited, v):
    visited[v] = 1
    ans.append(v)

    for nv in graph[v]:
        if visited[nv] == 0:
            dfs_rec(graph, visited, nv)

dfs_rec(graph, visited, v)
print(' '.join(map(str, ans)))

# bfs
from collections import deque
ans = []
visited = [0] * (n+1)
queue = deque()
def bfs_que(graph, visited, v):
    queue.append(v)
    visited[v] = 1
    
    while queue:
        n = queue.popleft()
        ans.append(n)
        for nv in graph[n]:
            if visited[nv] == 0:
                queue.append(nv)
                visited[nv] = 1

bfs_que(graph, visited, v)
print(' '.join(map(str, ans)))