DFS(Depth-First Search)
○ DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다.
○ DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같습니다.
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문
처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.
★더 자세한 내용은 아래의 동영상 참조
[이것이 코딩 테스트다 with Python] 18강 DFS 알고리즘 - YouTube
BFS(Breadth-First Search)
○ BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다.
○ DFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같습니다.
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문
처리합니다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.
★더 자세한 내용은 아래의 동영상 참조
[이것이 코딩 테스트다 with Python] 19강 BFS 알고리즘 - YouTube
https://www.acmicpc.net/problem/1388
1388번: 바닥 장식
형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나
www.acmicpc.net
바닥 장식 문제를 bfs를 이용해서 풀어볼려고 노력해보았지만 실패를 하여 이중반복문을 이용해서 코드구현을 하였다.
https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
바이러스 문제를 풀면서 공부를 했던 bfs/dfs가 이렇게 사용될 수 있는 지를 약간 이해하게되었다. 이 바이러스 문제에서의 놓치지 말아야 할 부분은 마지막 부분에 만약 sum(visited)를 하게 되면 1번 컴퓨터를 포함한 방문 표시된 컴퓨터들의 개수가 나온다. 그러므로 1번 컴퓨터를 제외하고 출력하기 위해서 (visited)-1을 해야한다.
https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
이 문제는 DFS와 BFS의 기본 개념을 한번더 이해 할 수 있는 문제인 것 같다. DFS는 재귀로 구현하고 BFS는 queue로 구현하는 게 보통이다. 정점을 이용한 방식을 이용하였으므로 오름차순 정렬이 필요하다.
https://www.acmicpc.net/problem/11725
11725번: 트리의 부모 찾기
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
www.acmicpc.net
이 문제는 실질적으로 문제는 이해하지 못하였고, 그냥 코드적인 부분으로 접근을 하여 해결하려고 노력하였다.
아직도 BFS와 DFS가 확실히 이해가 되지는 않지만 기본적인 코드 맥락은 어느정도 이제 파악이 되는 수준인것 같다. 처음에 20강 강의의 예제 문제들을 이해해 보면서 전체적인 DFS와 BFS의 코드 맥락을 파악해볼려고 노력하였고, 실제 문제를 풀때 틀을 비슷하게 가져가보면서 응용을 시도해보았다.
'FOSCAR-(Autonomous Driving) > 알고리즘 스터디' 카테고리의 다른 글
| [2023 알고리즘 스터디] 3조 박제형 5주차 - 정렬 (1) | 2023.02.25 |
|---|---|
| [2023 알고리즘 스터디] 3조 선병범 4주차 - DFS & BFS 알고리즘 (1) | 2023.02.20 |
| [2023 알고리즘 스터디] 5조 #4주차 - DFS & BFS 알고리즘 (1) | 2023.02.19 |
| [2023 알고리즘 스터디] 4조 변준형 4주차 - 백준 7562 (1) | 2023.02.19 |
| [2023 알고리즘 스터디] 1조 김동훈 4주차 - 백준 1388 2606 1260 2644 (1) | 2023.02.17 |
