| 작성자 | 이재영 |
| 일 시 | 2024. 9. 19 (목) 18:00 ~ 21:00 |
| 장 소 | 복지관 b-128호 |
| 참가자 명단 | 임혜진, 이재영, 성창민, 김명원, 장원준 |
| 사 진 |  |
더보기
목차
- DFS란?
- DFS 백준 풀이
- BFS란?
- BFS 백준 풀이
이번 주차에서는 지난 주차에서 공부한 Stack, Queue를 활용한 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)에 대해서 알아보고, 백준도 풀어보려고 한다.
1. DFS란?
깊이 우선 탐색(Depth-First Search, DFS)란 그래프 탐색 방법 중 하나이다. 루트 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 즉, 정점에서 자식들을 우선으로 탐색하는 알고리즘이라고 생각하면 쉽다. 더 쉽게 예시를 들자면, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다른 방향으로 탐색을 진행하는 방식을 생각하면 될 것이다.
DFS의 특징은 다음과 같다.
- 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
- 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
- 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
- 주로 Stack을 사용한다.
2. DFS 백준 풀이
import java.util.Scanner;
public class _2606 {
// DFS 메서드를 사용하기 위해 전역으로 선언
// visited는 방문 여부를 확인하는 배열
static boolean[] visited;
// list는 컴퓨터와 네트워크로 연결되어 있는 컴퓨터 쌍의 정보를 저장하는 2차원 배열
static int[][] list;
// n은 전체 컴퓨터의 수, t는 컴퓨터 쌍의 개수, count는 바이러스에 감염되는 컴퓨터의 수를 셀 변수
static int n, t, count = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 컴퓨터의 수 입력
n = sc.nextInt();
// 네트워크 연결 쌍의 개수 입력
t = sc.nextInt();
// 컴퓨터 번호는 1번부터 시작하므로 크기가 n+1인 배열을 선언
visited = new boolean[n+1];
list = new int[n+1][n+1];
// 네트워크 연결 정보를 입력받음
for (int i = 0; i < t; i++) {
int node = sc.nextInt(); // 첫 번째 컴퓨터
int node2 = sc.nextInt(); // 두 번째 컴퓨터
// 양방향 연결이므로 두 컴퓨터 간의 연결을 각각 설정
list[node][node2] = list[node2][node] = 1;
}
// 1번 컴퓨터부터 DFS 탐색 시작 (문제에서 1번 컴퓨터가 감염된다고 가정)
DFS(1);
// 감염된 컴퓨터 수 출력 (1번 컴퓨터는 제외하므로 count-1)
System.out.println(count - 1);
}
// 깊이 우선 탐색(DFS)을 통해 네트워크를 탐색하는 메서드
static void DFS(int x) {
// 현재 컴퓨터를 방문 처리
visited[x] = true;
// 감염된 컴퓨터 수 증가
count++;
// 모든 컴퓨터에 대해 연결 여부를 확인
for (int i = 0; i <= n; i++) {
// 아직 방문하지 않았고, 현재 컴퓨터(x)와 연결된 컴퓨터(i)가 있다면 재귀 호출
if (!visited[i] && list[x][i] == 1) {
DFS(i);
}
}
}
}
3. BFS란?
너비 우선 탐색(Breadth-First Search, BFS)란 그래프 탐색 방법 중 하나이다. 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 즉, 정점에서 가까운 정점을 먼저 방문하는 방식으로 탐색하는 알고리즘이라고 생각하면 쉽다.
BFS의 특징은 다음과 같다.
- DFS와 다르게 재귀적으로 동작하지 않는다.
- 어떤 노드를 방문했었는지 여부를 반드시 검새해야 한다.
- 직관적이지 않은 면이 있다.
- 주로 Queue를 사용한다.
4. BFS 백준 풀이
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class _2178 {
// BFS를 함수로 만들 것이기 때문에 사용할 배열, 변수 등을 전역으로 선언한다.
static int n, m;
static int[][] list;
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
list = new int[n][m];
visited = new boolean[n][m];
// list에 값을 입력받을 때 문제에서 각각의 수들은 붙여서 주어진다고 했기 때문에
// 문자열로 받아 그 문자열을 한글자 씩 떼어 리스트에 넣어준다.
for(int i=0;i<n;i++){
String line = sc.next();
for(int j=0;j<m;j++){
list[i][j] = line.charAt(j)-'0';
}
}
// 0,0 부터 시작할 것이기 때문에 BFS 로직을 위해 true로 값을 설정해두고 시작한다.
visited[0][0] = true;
// 초기 좌표값 0, 0을 넣어주며 BFS 시작
BFS(0,0);
// BFS 함수가 끝나면 문제에서 구하려 했던 마지막 좌표값에 값은 초기 0,0 에서 걸리는 좌표값이 되어 있을 것이다.
System.out.println(list[n-1][m-1]);
}
static void BFS(int x, int y){
// Queue를 선언하고 초기값으로 x,y를 배열로 넣어준다. (0, 0) 좌표 형식
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{x, y});
// Queue가 값이 없을 때까지 반복
while(!queue.isEmpty()){
// 선입선출인 Queue 특징에 따라 front에 있는 좌표를 하나 빼온다.
int[] cur = queue.poll();
int x_ = cur[0];
int y_ = cur[1];
// 상,하,좌,우 좌표값을 하나 씩 넣어주기 위해 4번 반복해준다.
for(int i=0;i<4;i++){
// (-1,0), (1,0), (0,-1), (0,1)
int nextX = x_ + dx[i];
int nextY = y_ + dy[i];
// 좌표값의 유효성을 검사한다. 상,하,좌,우에 좌표값이 주어진 미로에 벗어날 경우.
if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m)
continue;
// 주어진 좌표 또는 상,하,좌,우에 좌표값이 이미 방문한 곳인 경우
if (visited[nextX][nextY] || list[nextX][nextY] == 0)
continue;
// 유효성 검사에 통과하면 그 좌표를 queue에 넣어둔다.
queue.add(new int[] {nextX, nextY});
// 그리고 그 좌표값에 기존 좌표값 + 1 한 값을 넣어주는데
// 좌표값까지 오는데 지나야 하는 칸수를 뜻한다.
list[nextX][nextY] = list[x_][y_] + 1;
// 방문한 좌표값을 표시해준다.
visited[nextX][nextY] = true;
}
}
}
}Stack과 Queue에 대해서 개념만 할 때는 몰랐는데 실제 활용을 하니 생각보다 너무 어려웠다. Java 언어의 난이도가 많이 높아서 놀랐고, 기초를 좀 더 다져야 하겠다고 느꼈다.