코테 문제를 풀면서 내가 실수를 하는 부분은 크게 2가지다.
- 변수 크기 잘못 설정
- for loop 변수 이름 (중첩 for loop을 다 i로 한다던지...) 혹은 범위 잘못 설정
문제 링크: DFS와 BFS
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
.
.
문제 풀이 과정
일단 오랜만에 다시 코테 문제들을 푸는 과정이라 쉬운 문제부터 차근차근 푸는 중이다.
DFS (깊이 우선 탐색)
- 재귀함수나 스택을 이용한다.
BFS (너비 우선 탐색)
- 큐를 이용한다.
이 부분은 코드를 통해 더 자세하게 설명해보겠다.
.
.
code(1) - input 받기
input을 받는 부분에서 놓쳐서는 안되는 부분이 있다.
보통 문제에 내가 bold 처리해둔 것을 잘 보면 코딩에 챙겨야 할 부분들이 명시되어 있다.
방문할 정점이 여러개인 경우에는 정점번호가 작은 것부터 방문하라고 되어있으므로
노드별로 연결된 노드를 push_back으로 넣어준 후 sort를 통해 정렬을 해주어야 한다.
또한 이 정렬을 할 때 노드별로 하나씩 진행하는데 여기서 주의할 부분은 for loop의 idx가 곧 노드의 번호라는 점이다. 따라서 1부터 시작해야 한다.
아래 코드를 진행하고 나면 아래와 같이 graph에 저장된다고 생각하면 된다.
예제 1번을 기준으로
graph[1] = {2, 3, 4}
graph[2] = {1, 4}
graph[3] = {1, 4}
graph[4] = {1, 2, 3}
void input()
{
cin >> n >> m >> start_point;
for (int i = 1; i <= m; i++)
{
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
for (int i = 1; i <= n; i++)
{
sort(graph[i].begin(), graph[i].end());
}
}
.
.
code(2) - DFS
DFS는 깊이 우선 탐색으로 기준 노드에서 탐색할 수 있는 가장 깊은 노드까지 갔다가 돌아와 탐색하는 방식이다.
스택이나 재귀함수를 이용해 구현할 수 있다.
나는 재귀함수로 구현하였다.
일단 작동 방식을 설명하자면
예제 1을 기준으로
1번이 start이므로
1. 1번 노드 방문처리
2. 1번 노드 출력
3. 1번 노드와 연결된 노드 차례대로 방문 (위 input 함수에서 오름차순으로 정렬)
4. 방문 안한 경우 재귀함수(방문처리, 출력, 연결된 노드 차례대로 방문)
이런 방식으로 진행된다.
따라서 1 → 2 → 4 → 3
< 그래프 형태 >
graph[1] = {2, 3, 4}
graph[2] = {1, 4}
graph[3] = {1, 4}
graph[4] = {1, 2, 3}
dfs(1) -> dfs(2) -> dfs (4) -> dfs(3)
재귀함수의 흐름을 나타내자면 이런 형태 인 것이다.
dfs(2)에서 dfs(4)로 넘어가는 이유는 1은 이미 방문하여 방문처리 되었기 때문이다.
void dfs(int start)
{
visited[start] = true;
cout << start << ' ';
for (int i = 0; i < (int)graph[start].size(); i++)
{
int y = graph[start][i];
if (!visited[y])
dfs(y);
}
}.
.
code(3) - BFS
BFS는 큐를 사용한다.
방문하고자 하는 노드와 연결된 노드 중에서 방문하지 않은 노드를 모두 큐에 넣고
큐에서 하나씩 꺼내어 연결된 노드를 찾는 방식이다.
예시 1을 기준으로 설명해보자면
< 그래프 형태 >
graph[1] = {2, 3, 4}
graph[2] = {1, 4}
graph[3] = {1, 4}
graph[4] = {1, 2, 3}
- 1번 노드 방문
- queue에 1번 노드와 연결된 노드 중 방문하지 않은 노드 넣고 방문처리하기
q = {2, 3, 4} - queue에서 앞에서부터 빼면서 출력, 또 연결된 노드 중 방문하지 않은 노드 큐에 넣기 (예시1에서는 없음)
void bfs(int start)
{
visited_b[start] = true;
q.push(start);
while (!q.empty())
{
int x = q.front();
q.pop();
cout << x << ' ';
for (int i = 0; i < (int)graph[x].size(); i++)
{
int y = graph[x][i];
if (!visited_b[y])
{
visited_b[y] = true;
q.push(y);
}
}
}
}전체 코드(cpp)
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
//initialization
int n;
int m;
int a, b;
int start_point;
vector<int> graph[1001];
bool visited[1001];
bool visited_b[1001];
queue<int> q;
void input()
{
cin >> n >> m >> start_point;
for (int i = 1; i <= m; i++)
{
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
for (int i = 1; i <= n; i++)
{
sort(graph[i].begin(), graph[i].end());
}
}
void dfs(int start)
{
visited[start] = true;
cout << start << ' ';
for (int i = 0; i < (int)graph[start].size(); i++)
{
int y = graph[start][i];
if (!visited[y])
dfs(y);
}
}
void bfs(int start)
{
visited_b[start] = true;
q.push(start);
while (!q.empty())
{
int x = q.front();
q.pop();
cout << x << ' ';
for (int i = 0; i < (int)graph[x].size(); i++)
{
int y = graph[x][i];
if (!visited_b[y])
{
visited_b[y] = true;
q.push(y);
}
}
}
}
int main()
{
input();
dfs(start_point);
cout << endl;
bfs(start_point);
return 0;
}
.
.
.
.
전체코드 (python)
코테를 준비하다보니 python으로도 문제를 풀어보고있다.
from sys import stdin
from collections import deque
# func
def dfs(start):
visited[start] = True
print(start, end=" ")
for alpha in graph[start]:
if not visited[alpha]:
dfs(alpha)
def bfs(start):
visited2[start] = True
q = deque([start])
while q:
alpha = q.popleft()
print(alpha, end=" ")
for i in graph[alpha]:
if not visited2[i]:
visited2[i] = True
q.append(i)
# input
node, line, stp = map(int, stdin.readline().split())
graph = [[] for _ in range(node+1)]
visited = [False] * (node+2)
visited2 = [False] * (node+2)
for _ in range(line):
x,y = map(int,stdin.readline().split())
graph[x].append(y)
graph[y].append(x)
for i in graph:
i.sort()
dfs(stp)
print()
bfs(stp)