백준 - DFS와 BFS[1260] (DFS/BFS)
이번 포스팅에서는 백준 알고리즘의 DFS와 BFS[1260](DFS/BFS) 코딩테스트 연습 문제를 풀어봅니다.
문제 설명
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
입출력 예
| 입력 | 출력 |
|---|---|
|
4 5 1 1 2 1 3 1 4 2 4 3 4 |
1 2 4 3 1 2 3 4 |
|
5 5 3 5 4 5 2 1 2 3 4 3 1 |
3 1 2 5 4 3 1 4 2 5 |
|
1000 1 1000 999 1000 |
1000 999 1000 999 |
문제 풀이
먼저 첫번째 입력을 확인해 보면 정점의 개수:4, 간선의 개수:5, 시작 정점번호:1이고 간선이 연결하는 두 정점이 각각 1-2 1-3 1-4 2-4 3-4로 표현될때
DFS 탐색으로 확인하면 다음과 같습니다.
또한 BFS 탐색으로 확인하면 다음과 같습니다.
풀이 과정은 아래와 같습니다.
- 문제의 입력 방식이 첫째줄에서 정점의 개수, 간선의 개수, 시작 정점을 입력 받습니다.
- 둘째줄 부터는 간선정보 임으로 첫째줄에서 간선의 개수만큼 리스트에 추가 합니다.
- dfs와 bfs탐색의 차이는 ‘stack’저장 또는 ‘queue’저장 방식의 차이가 있음으로 둘다 사용 가능한 ‘deque’를 이용하여 같은 로직에서 flag 변화만 줘서 동작 할 수 있도록 합니다.
- 루프는 정점의 개수 만큼 탐색을 수행합니다.
- 루프를 수행하면서 현재 정점 데이터(첫 루프시에는 시작 정점)를 저장하고 현재 정점은 검색 완료된 값으로 인식 할 수 있도록 리스트를 생성 후 플래그를 변경 합니다.
- 간선 리스트는 방향성이 없음으로 첫번째 값이 현재 정점과 일치할 경우 두번째 값이 연결된 다른 정점이 되며 반대로 두번째 값이 일치할 경우 첫번째 값이 연결된 다른 정점이 됩니다. 이때 이미 검색이 완료된 값은 제외 합니다.
- 위에서 찾은 연결된 다른 정점들은 리스트로 저장합니다.
- 연결된 다른 정점 리스트는 dfs 일땐 우선 탐색할 정점을 마지막으로 정렬하고 bfs일 경우는 처음으로 정렬 합니다.
- 정렬된 리스트를 deque에 추가 합니다.
- 만일 deque리스트에 값이 존재 하지 않으면 연결된 간선이 더이상 존재 하지 않거나 모든 탐색이 완료된 상태임으로 루프를 종료 합니다.
- 루프의 마지막에서 dfs일 경우 ‘stack’방식으로 가장 나중에 저장된 정점을 빼서 현재 탐색 정점으로 저장하고 bfs의 경우 ‘queue’방식으로 가장 처음에 저장된 정점을 빼서 현재 탐색 정점으로 저장합니다.
- 루프가 종료되면 저장된 값을 반환합니다.
from sys import stdin
from collections import deque
# 입력
info = list(map(int,stdin.readline().split()))
lineList = []
for i in range(info[1]): # 2번째 인자값인 간선의 개수만큼 리스트 추가
lineList.append(list(map(int, stdin.readline().split())))
def dfs_bfs(flag):
global info, lineList
answer = ''
searchList = [False] * info[0] # 정점의 개수 만큼 탐색 여부 리스트 추가
dequelist = deque() # dfs 탐색 또는 bfs 탐색을 위한 deque 리스트
now = info[2] # 처음 루프 수행 시에는 현재 정점이 시작 정점
for _ in range(info[0]): # 정점의 개수 만큼 검색 수행
answer += str(now) + ' ' # 현재 정점 데이터 저장
searchList[now - 1] = True # 현재 정점은 검색 완료된 값으로 변경
# 현재 값과 연결된 다른 정점 찾기
peaks = []
for l in lineList:
if l[0] == now: # 라인리스트에서 첫번째 값이 일치하면
if not searchList[l[1] - 1]: # 두번재 값이 이미 검색 완료된 값이 아니면
peaks.append(l[1]) # 두번째 값이 연결된 다른 정점
if l[1] == now: # 라인리스트에서 두번째 값이 일치하면
if not searchList[l[0] - 1]: # 첫번재 값이 이미 검색 완료된 값이 아니면
peaks.append(l[0]) # 첫번째 값이 연결된 다른 정점
peaks.sort(reverse=(True if flag == 'dfs' else False)) # dfs 에서는 우선 탐색할 정점을 마지막으로 정렬 반대의 경우 bfs
dequelist.extend(peaks) # dequelist에 연결된 정점 추가
if len(dequelist) == 0: # 간선이 없거나 더 이상 탐색할 정점이 없다면 루프 종료
break
if flag == 'dfs':
now = dequelist.pop() # dequelist에서 stack 방식으로 가장 나중에 저장된 정점을 빼서 다음 검색 대상으로 저장
elif flag == 'bfs':
now = dequelist.popleft() # dequelist에서 queue 방식으로 가장 처음에 저장된 정점을 빼서 다음 검색 대상으로 저장
return answer.rstrip()
print(dfs_bfs('dfs'))
print(dfs_bfs('bfs'))
5 5 3
5 4
5 2
1 2
3 4
3 1
3 1 2 5 4
3 1 4 2 5
결과는 아래와 같이 잘 통과 되는 것을 확인 할 수 있습니다.