[bfs/백준] 1260번 : DFS와 BFS

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

 

보기에는 간단한 것 같은데 생각을 좀 해야하는 문제였다. 

 

문제 이해

- dfs, bfs 함수를 각각 구현해야 하는 문제이다.

- 각 함수에서 지나는 노드들을 dfs, bfs 별로 순차적으로 출력해야한다.

- 연결된 노드 중에서 작은 값 순서대로 진행해야 한다고 나와있어 각 graph 원소마다 sort()를 해줘야 한다. 

- 지나는 노드들은 배열에 저장하는데 함수별로 arr_dfs, arr_bfs를 전역변수로 지정해 함수가 끝나도 배열이 유지될수 있게 한다. 

- 배열은 [a, b, c] 형태인데 정답은 a b c 형태로 출력해야하므로 마지막에 for문으로 정답에 맞는 형식으로 출력한다. 

- 각 함수마다 사용하는 visit가 다르므로 dfs, bfs 별로 visit를 따로 설정해줘야 한다. 

 

정답 풀이 

n, m, v = map(int, input().split())

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()
    
def dfs(node, arr, visit):
    visit[node] = 1
    for each in graph[node]:
        if not visit[each]:
            arr.append(each)
            dfs(each, arr, visit)


def bfs(node, arr, visit):
    queue = [node]
    visit[node] = 1
    
    while queue:
        x = queue.pop(0)
        for each in graph[x]:
            if not visit[each]:
                visit[each] = 1
                arr.append(each)
                queue.append(each)

arr_dfs = [v]
visit = [0] * (n + 1)
dfs(v, arr_dfs, visit)

arr_bfs = [v]
visit = [0] * (n + 1)
bfs(v, arr_bfs, visit)

for i in range(len(arr_dfs)):
    print(arr_dfs[i], end = ' ')
print()
for i in range(len(arr_bfs)):
    print(arr_bfs[i], end = ' ')