728x90
백준에서 처음으로 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)
1. 행렬 만들기
행렬을 만들 때 자주 사용되는 리스트 컴프리헨션 문법을 사용한다.
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] * (4)] 이므로 => [[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 반복문을 달출한다.728x90
'CodingTest > [Baekjoon Online Judge]' 카테고리의 다른 글
| 11053. 가장 긴 증가하는 부분 수열 (0) | 2024.06.14 |
|---|---|
| 7568 덩치 - 파이썬 (0) | 2024.03.12 |
| 4673 셀프넘버 - 파이썬 (0) | 2024.03.11 |
| 백준 1157번 [파이썬] 단어 공부 (0) | 2023.04.13 |
| 백준 10988번 [파이썬] 팰린드롬인지 확인하기 (0) | 2023.03.31 |
