📜 문제
- 문제 이름에서 알 수 있듯이 양방향 그래프가 주어지면
DFS,BFS각각의 방법으로 방문하는 정점을 출력하면 된다. - 단, 정점 방문 시 작은 숫자부터 방문
생각하기
솔직히 컴공 졸업했으면 이거 고민하면 안 된다~ 난 컴공 탈락
몇 개월 전만 해도 BFS, DFS 로직 바로 구현이 가능했는데, 오래 안 만졌다고 그새 까먹는 건
반성 많이 해야 합니다. 오늘 제대로 공부했으니 그래두 ㄱㅊ아
다음에 까먹으면 걍 죽으면 됨
개념을 알면 풀 수 있기에 생각할 게 따로 있는 건 아니고,
DFS, BFS를 설명하려 한다.
1. DFS
DFS는 Depth-First Search의 약어로 깊이 우선 탐색이라고 한다.
이름에서 어떤 친구인지 대충 유추가 가능하지만, 백문이불여일견
1번부터 시작한다고 가정했을 때, 1번 정점과 연결 된 친구들 탐색(1번 방문 처리)2번,3번,4번이 연결 됐지만, 가장 작은 숫자를 탐색한다고 하면,2번으로 이동2번정점과 연결된 친구들 탐색 (방문 처리가 되지 않은 정점만 탐색)- 이미 방문한
1번을 제하고,4번으로 이동(2번 방문 처리) 4번정점과 연결된 친구들 탐색- 마찬가지로 이미 방문한
1번,2번을 제하고 3번으로 이동(4번 방문처리) 3번정점과 연결된 다른 모든 정점이 모두 방문 됐으므로 종료.
따라서 1, 2, 4, 3 순서로 DFS가 구현된다.
만일, 4번 정점과 연결된 5번이 있다면, 방문 순서는 1, 2, 4, 3, 5가 된다.
즉, 현재 정점에서 이동할 수 있는 여러 정점이 있더라도,
다른 정점으로 계속 이동하고 난 후 다시 돌아와서 방문하는 개념이다.
BFS와 같이 보면 더 쉬울 거다.
2. BFS
BFS는 Breadth-First Search의 약어로 너비 우선 탐색이라고 한다.
마찬가지로.. 같은 그림을 보여주고 설명해조야지
비슷하게 생겼지만, 설명을 보면 다르다.
1. 1번 부터 시작한다고 가정했을 때, 1번 정점과 연결 된 친구들 탐색 (1번 방문 처리)
2. 작은 숫자부터 2번, 3번, 4번 방문할 예정 (모두 방문 처리)
3. 2번 정점과 연결된 미방문 친구들 탐색
4. 3번 정점과 연결된 미방문 친구들 탐색
5. 4번 정점과 연결된 미방문 친구들 탐색
6. 연결된 모든 정점을 방문했으므로 종료.
따라서 1, 2, 3, 4 순서대로 BFS가 구현된다.
만일, 2번에 5번 정점이 연결된 경우, 1, 2, 3, 4, 5 순서가 된다.
즉, 현재 정점과 연결된 정점들을 우선으로 탐색하는 개념이다.
조금 이해가 되려나ㅎ..
중요한 건 위 로직을 코드로 구현하는 방법이니까 함 설명해 보겠다.
🍳 전체 소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main{
static boolean[] visited;
static StringBuilder sb;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int start = Integer.parseInt(st.nextToken());
Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
visited = new boolean[n+1];
sb = new StringBuilder();
while (e -- >0){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
PriorityQueue<Integer> list = map.getOrDefault(a, new PriorityQueue<>());
list.add(b);
map.put(a,list);
list = map.getOrDefault(b, new PriorityQueue<>());
list.add(a);
map.put(b,list);
}
dfs(map, start);
sb.append("\n");
visited = new boolean[n+1];
bfs(map,start);
System.out.println(sb.toString());
}
public static void dfs(Map<Integer, PriorityQueue<Integer>> map, int current){
visited[current]=true;
sb.append(current+" ");
if(map.get(current) == null){
return;
}
PriorityQueue<Integer> pq = new PriorityQueue<>(map.get(current));
while(!pq.isEmpty()){
int v = pq.poll();
if(!visited[v]){
dfs(map, v);
}
}
return;
}
public static void bfs(Map<Integer, PriorityQueue<Integer>> map, int start){
Queue<Integer> que = new ArrayDeque<>();
que.add(start);
visited[start]=true;
while (!que.isEmpty()){
int cur = que.poll();
sb.append(cur+" ");
if(map.get(cur)==null){
continue;
}
PriorityQueue<Integer> pq = map.get(cur);
while(!pq.isEmpty()){
int v = pq.poll();
if(!visited[v]){
visited[v]=true;
que.add(v);
}
}
}
}
}
함수별로 살펴보자
✍ 부분 코드 설명
Main 함수 - 입력 & 변수 초기화
public class Main{
static boolean[] visited;
static StringBuilder sb;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int start = Integer.parseInt(st.nextToken());
Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
visited = new boolean[n+1];
sb = new StringBuilder();
while (e -- >0){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
PriorityQueue<Integer> list = map.getOrDefault(a, new PriorityQueue<>());
list.add(b);
map.put(a,list);
list = map.getOrDefault(b, new PriorityQueue<>());
list.add(a);
map.put(b,list);
}
dfs(map, start);
sb.append("\n");
visited = new boolean[n+1];
bfs(map,start);
System.out.println(sb.toString());
}
...
n: 정점 개수e: 간선 개수start: 탐색 시작 위치map: 정점간 연결을 담는 map (key: 정점 value: 정점과 연결된 다른 정점 list)visited: 정점의 방문 여부 확인
그 간선 수만큼 연결 관계를 입력 받잖아요?
그런데 양방향 연결이니까, 들어오는 두 개의 정점이 서로의 key, value 둘 다 해조야 합니다.
value 리스트로 우선순위 큐를 쓴 이유는 문제에서 정점 번호가 작은 순서대로 방문하라고 했기에 써줬구요.
ArrayList로 했다가, 하나 하나 다시 정렬하자니 머리 아프더라구요
그렇게 입력을 받고난 후 dfs, bfs 함수를 호출합니다.
dfs 함수
public static void dfs(Map<Integer, PriorityQueue<Integer>> map, int current){
visited[current]=true;
sb.append(current+" ");
if(map.get(current) == null){
return;
}
PriorityQueue<Integer> pq = new PriorityQueue<>(map.get(current));
while(!pq.isEmpty()){
int v = pq.poll();
if(!visited[v]){
dfs(map, v);
}
}
return;
}
bfs와 다른 점이 있다면, 재귀 호출 로 이루어진다는 점?
왜냐 우린 깊이 깊이 들어가야 하니까..
- 우선 current로 들어온 현재 정점을 방문 처리 하고 시작한다.
- 만일, current 정점과 연결된 다른 정점이 없는 경우
return - 현재 정점과 연결된 다른 정점들을 pq에 저장
- pq에서 하나씩 빼서 방문하지 않은 노드가 있다면, 해당 노드를
current로 dfs 호출 - 위 과정 반복
bfs 함수
public static void bfs(Map<Integer, PriorityQueue<Integer>> map, int start){
Queue<Integer> que = new ArrayDeque<>();
que.add(start);
visited[start]=true;
while (!que.isEmpty()){
int cur = que.poll();
sb.append(cur+" ");
if(map.get(cur)==null){
continue;
}
PriorityQueue<Integer> pq = map.get(cur);
while(!pq.isEmpty()){
int v = pq.poll();
if(!visited[v]){
visited[v]=true;
que.add(v);
}
}
}
}
bfs는 선입선출 의 특징을 가진 큐를 가지고 구현합니다.
- que 선언 및, start 정점 삽입
- start 정점을 방문 처리
- que에서 앞에 있는 정점 빼내어
cur변수에 저장 - 만일 cur 정점과 연결된 다른 정점이 없는 경우, que에서 다른 정점 빼내기
- 연결된 정점이 있는 경우, 연결된 모든 정점을 que에 삽입 및 방문 처리
- que가 빌 때까지 위 과정 반복
기억해야 할 점은 que에 넣으면서 방문 처리까지 해주는 거?
중복 삽입이 될 수 있기에..
ex)
1-2,4
2-3,4이렇게 연결 돼 있다고 하면
1번 정점에서 4번 정점이 이미 연결돼 방문할 예정이므로
2번 정점에선 4번 정점을 무시해야합니다~
✨ 결과
까먹어서 나에게 실망했지만,,
그만큼 중요한 개념이기때문에, 또 공부해서 리마인드 했으니 오히려 좋다.
그 나중에 응용 문제 많이 나오니까 또 까먹지 말자~
