[백준] 1260번 DFS와 BFS
https://www.acmicpc.net/problem/1260
문제설명 📖
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
입출력 예
문제접근 💡
DFS/BFS의 가장 기본적인 문제이다. 깊이우선탐색과 너비우선탐색, 스택, 큐의 개념이 있다면 쉽게 풀 수 있다.
이 문제를 검색해서 들어온 사람이라면 아직 개념이 잘 안잡혔을 수 있다.
위의 개념들이 충분히 숙지되지 않았다면 아래 링크를 참고하길 바란다.
👉🏻 https://velog.io/@falling_star3/2.-깊이우선탐색DFS과-넓이우선탐색BFS
문제풀이 💡
N,M,V = map(int,input().split())
#행렬 만들기
graph = [[0]*(N+1) for _ in range(N+1)]
for i in range (M):
a,b = map(int,input().split())
graph[a][b] = graph[b][a] = 1
#방문 리스트 행렬
visited1 = [0]*(N+1)
visited2 = visited1.copy()
#dfs 함수 만들기
def dfs(V):
visited1[V] = 1 #방문처리
print(V, end=' ')
for i in range(1, N+1):
if graph[V][i] == 1 and visited1[i] == 0:
dfs(i)
#bfs 함수 만들기
def bfs(V):
queue = [V]
visited2[V] = 1 #방문처리
while queue:
V = queue.pop(0) #방문 노드 제거
print(V, end = ' ')
for i in range(1, N+1):
if(visited2[i] == 0 and graph[V][i] == 1):
queue.append(i)
visited2[i] = 1 # 방문처리
dfs(V)
print()
bfs(V)문제해설 💡
백준에서 처음으로 DFS/BFS 문제를 접한 사람들을 위해 최대한 자세하게 해설을 적어보았다.
알고리즘 문제를 접하면서 이 유형이 제일 어려웠기 때문에 나처럼 많이 헤매고 있는분이 계시다면 부디 이 포스팅이 도움이 되기를 바란다.
1. 행렬 만들기
이 코드를 이해하기 위해서는 행렬을 만들 때 주로 쓰는 리스트 컴프리헨션 문법을 알고 있어야 한다.
👉🏻 https://velog.io/@falling_star3/Python-리스트-컴프리헨션Comprehension
graph = [[0]*(N+1) for _ in range(N+1)]
for i in range (M):
a,b = map(int,input().split())
graph[a][b] = graph[b][a] = 1[[0]*(N+1)] 은 N이 3이라면 [[0,0,0,0]]을 출력한다.
리스트 컴프리헨션을 써주면 [[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]]행렬이 완성된다.
graph = 0 1 2 3 행
0 0 0 0 0
1 0 0 0 0
2 0 0 0 0
3 0 0 0 0
열
정점의 개수만큼의 행렬을 만들었다면,
이제는 정점 간의 연결을 행렬에 표시해 주어야한다.
만약 '1 2'가 입력된다면 정점1과 정점2가 연결되어있다는 뜻이므로 0을 1로 바꿔준다.
graph[1][2] = graph[2][1] = 1
graph = 0 1 2 3 행
0 0 0 0 0
1 0 0 1 0
2 0 1 0 0
3 0 0 0 0
열
2. 방문 리스트 만들기
BFS/DFS는 스택과 큐를 사용한다. 이 때, 스택과 큐에 한 번 들어갔던 노드는 다시 들어가지 못한다.
즉, 이 노드가 스택과 큐에 들어갔던적이 있는지를 확인할 필요가 있다. 이를 표현하기 위해 정점의 수만큼의 방문 리스트를 만들어보겠다.
visited1 = [0]*(N+1)
visited2 = visited1.copy()
N이 3이라면, visited1 = [0,0,0,0]
만약 1번 노드가 스택에 들어간 적이 있다면 visited = [0,1,0,0] 이 될 것이다.3. dfs 함수 만들기 (재귀이용)
def dfs(V):
visited1[V] = 1 #방문처리
print(V, end=' ')
for i in range(1, N+1):
if graph[V][i] == 1 and visited1[i] == 0:
dfs(i)
탐색을 시작하는 번호 V부터 탐색을 시작한다.
먼저 V노드가 시작이므로 V를 방문 처리한다.
예를들어 V=1이라면 위에서 만들어놓은 방문 리스트에서 visited1[1] = 1 로 방문처리하는 것이다.
그러면 visited1 = [0,1,0,0]이 될 것이다.
이는 1번 노드가 스택에 들어간적이 있다는 기록인 것이다.
1번 노드가 방문했으므로 1번 노드를 출력한다.
print(V, end=' ')
이 후 for문을 돌려서 if graph[V][i] == 1로
graph[1][1], graph[1][2], graph[1][3]을 확인해 줄 것이다.
이는 1과 연결된 노드를 찾는 것이다. (위에서 행렬로 연결된 노드들을 1로 표시해두었으므로)
만약 1과 2가 연결돼있다면 graph[1][2] == 1에 True가 될 것이다.
여기서 and visited1[i] == 0으로 2번 노드가 스택에 들어갔던 적이 있는지 확인해주어야 한다.
만약 2번 노드가 스택에 들어간적이 있다면 만들어놓은 방문리스트에서 1값으로 변경되었을 것이다.
즉, 1과 연결된 노드 중 방문기록이 없는 노드를 찾는 코드이다.
if graph[V][i] == 1 and visited1[i] == 0:
1과 연결된 노드 중 방문기록이 없는 노드가 있다면
dfs(i)로 재귀함수를 돌린다.
dfs(2)는 다시 위의 과정을 돌려서 2를 방문처리하고, 2와 연결된 노드를 찾는다.
이렇게 계속 연결된 노드들을 찾아 '깊이우선탐색'을 진행하는 것이다. 4. bfs 함수만들기
def bfs(V):
queue = [V]
visited2[V] = 1 #방문처리
while queue:
V = queue.pop(0) #방문 노드 제거
print(V, end = ' ')
for i in range(1, N+1):
if(graph[V][i] == 1 and visited2[i] == 0):
queue.append(i)
visited2[i] = 1 # 방문처리
bfs는 queue를 이용한다.
탐색 시작 노드 V가 주어진다면
queue = [V] 로 큐에 탐색 노드를 먼저 넣는다.
이 후, 위에서 만들어놓은 방문리스트 visited2[V] = 1로 방문 처리해준다.
V가 1이라면 visited2 = [0,1,0,0]이 될 것이다.
dfs와 같은 원리이다.
이제 while queue: 로 queue에 값이 없을때까지(탐색이 끝날때까지) 반복할 것이다.
먼저 queue.pop(0)을 해준다. 이 코드는 queue에서 0번째 요소를 돌려주고 삭제하라는 것이다.
queue는 선입선출 구조이므로 가장 먼저들어온 0번째 요소부터 빼는 것이다.
그리고 삭제한 요소를 V변수로 돌려받겠다.
위에서 V를 1로 가정했을 때 queue = [1], visited[2] = [0,1,0,0]인 상태이고
여기서 V = queue.pop(0)을 해주면 queue = []이 되고, V = 1이 될 것이다.
1을 뺐으니 1을 출력한다. print(V, end = ' ')
이 후 for문으로 연결된 노드들을 탐색해줄 것이다.
원리는 위에 설명한 dfs와 같다.
V와 연결되고, 방문한 적이 없는 노드가 있다면
큐에 넣어줄 것이다.
bfs과정을 나열해보겠다.
V = 1 // 1번 노드부터 탐색시작
queue = [1] // 방문 노드 저장
visited2[1] = 1 // visited2 = [0,1,0,0]
while문 들어가서,
queue = []
V = 1 // 1출력
for문 들어가서,
노드 1과 2가 연결되고, 노드 2가 방문된적이 없다면
graph[1][2] ==1 and visited2[2] == 0에 해당하므로
queue = [2]
visited2[2] = 1로 방문처리
노드 1과 3이 연결되고, 노드 3이 방문된적이 없다면
queue = [2,3]
visited2[3] = 1로 방문처리
모든 연결 노드 확인 후 for문 반복 끝
queue에 값이 있으므로
while문 탈출 안하고 다시 반복
V = 2 // 2출력
queue = [3]
graph[2][1] == 1 and visited2[2] ==0에 해당하지 않으므로 큐에 다시 넣지 못한다.(2는 1과 연결돼있지만, 1은 이미 큐에 들어간 기록이 있다.)
graph[2][3] == 1 and visited2[2] ==0 역시 마찬가지로 방문기록이 있으므로 false
이 경우 아무것도 추가되지 않고 for문을 빠져나간다.
queue = [3]으로 아직 값이 있으므로 while문 다시 반복
V = 3
queue = []
5. bfs함수 더 이해하기
queue는 pop(0)을 통해 먼저 들어온 요소를 뺀다.
선입선출인 큐가 너비우선탐색을 하게하는 핵심이다.
아래와 같이 연결된 노드가 있다고 가정해보자.
(1-2,1-3,1-4,3-5,4-6,6-7 연결)
1 - 2
- 3 - 5
- 4 - 6 - 7
queue에는 시작 노드를 먼저 담고 시작한다.
queue = [1]로 시작해서 1을 뺀 후 출력한다.
// queue = []
// 출력: 1
이 후 1과 연결된 2,3,4 가 queue에 담길 것이다.
// queue = [2,3,4]
0 번째 요소 (가장 먼저들어온) 2번 노드를 빼고 출력한다.
// 출력: 1 2
2와 연결된 노드를 확인한다.
2와 연결된 노드가 없다면 추가되지 않는다.
// queue = [3,4]에서
0 번째 요소 3번 노드를 빼고 출력한다.
// 출력: 1 2 3
3과 연결된 노드를 확인한다.
3과 연결된 5가 queue에 담길 것이다.
// queue = [4,5]
0 번째 요소 4번 노드를 빼고 출력한다.
// 출력: 1 2 3 4
4와 연결된 노드를 확인한다.
4와 연결된 6이 queue에 담길 것이다.
// queue = [5,6]
0 번째 요소 5번 노드를 빼고 출력한다.
// 출력: 1 2 3 4 5
5와 연결된 노드를 확인한다.
5와 연결된 노드가 없다면 추가되지 않는다.
// queue = [6]
0 번째 요소 6번 노드를 빼고 출력한다.
// 출력: 1 2 3 4 5 6
6과 연결된 노드를 확인한다.
6과 연결된 7이 queue에 담길 것이다.
// queue = [7]
0 번째 요소 7번 노드를 빼고 출력한다.
// 출력: 1 2 3 4 5 6 7
7과 연결된 노드를 확인한다.
7과 연결된 노드가 없다면 추가되지 않는다.
queue = [] 빈 문자열이므로 while 반복문을 달출한다.다른풀이 💡
# Depth First Search
def dfs(n):
print(n, end=' ')
visited[n] = True
for i in graph[n]:
if not visited[i]:
dfs(i)
# Breadth First Search
def bfs(n):
visited[n] = True
queue = deque([n])
while queue:
v = queue.popleft()
print(v, end= ' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
import sys
from collections import deque
# node, branch, first node
n, m, v = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
visited = [False] * (n + 1)
# make adjacency list
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
# sort adjacency list
for i in range(1, n+1):
graph[i].sort()
dfs(v)
# initialize check list
visited = [False] * (n + 1)
print()
bfs(v)
하이 이것은 나의 깨지고 부서지는 샏 스토리입니다
감사해요!