on
[백준(Baekjoon)] 1260 DFS와 BFS
[백준(Baekjoon)] 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
나의 풀이
[Python(파이썬)]
def dfs(x, check): check[x] = True # x 노드 방문 표시 print(x, end=' ') for k in glist[x]: # x 노드와 연결된 아직 방문하지 않은 노드를 재귀호출 if not check[k]: dfs(k, check) def bfs(x, check): queue = deque([x]) check[x] = True # x 노드 방문 표시 while queue: # 큐가 빌 때까지 k = queue.popleft() print(k, end=' ') for y in glist[k]: if not check[y]: # x 노드와 연결된 방문하지 않은 원소들을 큐에 삽입 queue.append(y) check[y] = True import sys from collections import deque input = sys.stdin.readline v, e, n = map(int, input().split()) glist = [[] for _ in range(v+1)] vsort = [] for _ in range(e): # 인접리스트 생성 i, j = map(int, input().split()) glist[i].append(j) glist[j].append(i) vsort.append(i) vsort.append(j) set(vsort) for i in vsort: # 간선이 있는 노드만 정렬 glist[i].sort() check = [False]*(v+1) dfs(n, check) print() check = [False]*(v+1) bfs(n, check)
풀이과정
1. 인접리스트 생성
2. DFS 구현
3. BFS 구현
1. 인접리스트 생성
입력으로 간선이 연결하는 두 정점의 번호가 주어지기 때문에 인접 리스트를 직접 생성해야 한다.
※ 인접리스트 생성 시 주의할 점
첫 번째 : 입력으로 주어지는 간선은 양방향이다.
두 번째 : 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다.
위의 두 가지가 인접리스트 생성할 때 중요하게 생각해야 할 점이다. 저 조건들을 생각하지 않고 구현해서 '틀렸습니다'를 보고 말았다.
위의 주의할 점을 생각하여 코드를 구현해보자.
glist = [[] for _ in range(v+1)] vsort = [] for _ in range(e): # 인접리스트 생성 i, j = map(int, input().split()) glist[i].append(j) glist[j].append(i) vsort.append(i) vsort.append(j) set(vsort) for i in vsort: # 간선이 있는 노드만 정렬 glist[i].sort()
1-1. 노드의 개수 + 1 만큼의 이차원 리스트 glist 초기화 ( 0은 비워두고 노드 개수만큼 리스트를 생성하기 위해 v+1)
1-2. 일차원 리스트 vsort 생성 (연결된 간선이 있는 노드 저장하는 리스트, 나중에 정렬하기 위함)
1-3. for문 e(간선의 개수) 만큼 1-[4~6] 반복
1-4. 간선이 연결하는 두 정점의 번호를 입력받아 i, j에 저장
1-5. 인접리스트에 간선 정보 저장
glist[i].append(j) # 노드 i에 대한 리스트에 j 저장 glist[j].append(i) # 노드 j에 대한 리스트에 i 저장
-> 입력으로 주어지는 간선은 양방향이기 때문에 각 각 저장을 해줘야한다.
1-6. vsort에 i, j 저장
1-7. vsort를 집합으로 변환 -> 여러번 저장된 노드를 한 번만 저장하기 위함
1-8. 간선의 정보를 가지고 있는 노드에 대한 리스트 정렬 -> 방문할 수 있는 정점이 여러개인 경우 정점의 번호가 작은 것부터 먼저 방문하기 위해 정렬해야한다.
for i in vsort: # 간선이 있는 노드만 정렬 glist[i].sort()
※ vsort를 구현한 이유
1부터 노드의 개수만큼 for문 돌려서 glist를 정렬할 수 있었지만 vsort를 구현한 이유는 시간을 줄이기 위함이다.
정점이 전부 간선으로 연결 된 것은 아니기 때문에 vsort에 간선을 가진 정점을 저장해 두면 그 정점의 리스트만 정렬할 수 있다.
ex) 1000 1 1000
999 1000이 입력일 때
1 ~ 1000까지 정렬해야하지만 vsort를 이용하면 999, 1000번의 정점 리스트만 정렬하여 1000번을 2번으로 줄일 수 있다.
[Algorithm] BFS, DFS (tistory.com)
2. DFS 구현
DFS는 stack이나 재귀 함수하여 구현 할 수 있다.
아래 코드는 재귀 함수를 이용하여 구현한 DFS 코드 이다.
def dfs(x, check): check[x] = True # x 노드 방문 표시 print(x, end=' ') for k in glist[x]: # x 노드와 연결된 아직 방문하지 않은 노드를 재귀호출 if not check[k]: dfs(k, check)
3. BFS 구현
BFS는 Queue를 이용하여 구현 할 수 있다.
def bfs(x, check): queue = deque([x]) check[x] = True # x 노드 방문 표시 while queue: # 큐가 빌 때까지 k = queue.popleft() print(k, end=' ') for y in glist[k]: if not check[y]: # x 노드와 연결된 방문하지 않은 원소들을 큐에 삽입 queue.append(y) check[y] = True
문제 출처
from http://young-library.tistory.com/157 by ccl(A) rewrite - 2021-11-09 23:01:24