[BOJ] 1260. DFS와 BFS

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

1260번: DFS와 BFS

 

1. 해결방법

"""
1. 아이디어
- 공통 : 방문기록(chk)가 중복되지 않도록 방문기록 2차원 배열을 2개 만듬.
- 공통 : 양방향 이동이 가능하기 떄문에 a vertex 위치에 b를 append 하는 배열과 b, a 반대도 똑같이 배열에 넣는다.
- BFS : 큐에 a와 b가 append괸 그래프 배열을 순서대로 삽입하고 방문한다. 방문기록도 False로 한다. 큐에 담겨진 vertex가 True이면 pass
- DFS : 재귀를 사용해서 방문기록을 False로 한다. True이면 pass

2. 시간복잡도
- 2차원 배열 : O(N^2)
- N^2 + M : 1000^2 + 10000

3. 자료구조
- 공통 : 2차원 배열 : inr[][], bool[][]
- DFS : 재귀
- BFS : Queue
"""

 

 

2. 정답 코드

입력 예제(1)

4 5 1
1 2
1 3
1 4
2 4
3 4

출력 예제(1)

1 2 4 3
1 2 3 4

 

입력 예제(2)

5 5 3
5 4
5 2
1 2
3 4
3 1

출력 예제(2)

3 1 2 5 4
3 1 4 2 5

 

입력 예제(3)

1000 1 1000
999 1000

출력 예제(3)

1000 999
1000 999

 

코드

import sys
from collections import deque

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

graph = [[] for _ in range(n+1)]
chk_dfs = [False] * (n + 1)
chk_bfs = [False] * (n + 1)
result_bfs = []
result_dfs = []

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


# bfs
def bfs(start):
    q = deque()
    q.append(start)
    result_bfs.append(start)
    chk_bfs[start] = True
    while q:
        now = q.popleft()
        for bfs_v in sorted(graph[now]):
            if chk_bfs[bfs_v] == False:
                chk_bfs[bfs_v] = True
                q.append(bfs_v)
                result_bfs.append(bfs_v)


# dfs
def dfs(start):
    chk_dfs[start] = True
    result_dfs.append(start)
    for dfs_v in sorted(graph[start]):
        if chk_dfs[dfs_v] == False:
            dfs(dfs_v)


# main
dfs(v)
for j in result_dfs:
    print(j, end=' ')
print()
bfs(v)
for i in result_bfs:
    print(i, end=' ')

 

DFS와 BFS의 결과 값을 둘 다 출력해야하므로 방문기록 chk[][]를 초기화를 하던가 두 개를 만들어야 한다.

또한, 입력 a와 b는 양방향으로 이동이 가능하므로 그래프 배열에 삽입할 때, a와 b에 각각 삽입해야 한다. (같은 그래프 배열에...)
어차피 방문기록이 True로 되어있으면 같은 vertex는 pass 되기 때문에 상관없다.