[JAVA] 백준 "DFS와 BFS"

전체코드

1. check / checked 배열

2. public static void dfs(int i)

3. public static void bfs()

https://www.acmicpc.net/problem/1260

 

가장 DFS와 BFS의 기본적인 유형이다.

 

살펴봐야할 포인트를 하나씩 짚어보겠다.

먼저 전체코드를 서두에 올려놓겠다.

 

전체코드

import java.io.*;
import java.util.*;

public class Main {
​​​​//함수에서 사용할 변수들
​​​​static int[][] check; //간선 연결상태
​​​​static boolean[] checked; //확인 여부
​​​​static int n; //정점개수
​​​​static int m; //간선개수
​​​​static int start; //시작정점

​​​​public static void main(String[] args) throws IOException {
​​​​​​​​Scanner sc = new Scanner(System.in);
​​​​​​​​n = sc.nextInt();
​​​​​​​​m = sc.nextInt();
​​​​​​​​start = sc.nextInt();

​​​​​​​​check = new int[1001][1001]; //좌표를 그대로 받아들이기 위해 +1해서 선언
​​​​​​​​checked = new boolean[1001]; //초기값 False

​​​​​​​​//간선 연결상태 저장
​​​​​​​​for (int i = 0; i < m; i++) {
​​​​​​​​​​​​int x = sc.nextInt();
​​​​​​​​​​​​int y = sc.nextInt();

​​​​​​​​​​​​check[x][y] = check[y][x] = 1;
​​​​​​​​}

​​​​​​​​dfs(start); //dfs호출

​​​​​​​​checked = new boolean[1001]; //확인상태 초기화
​​​​​​​​System.out.println(); //줄바꿈

​​​​​​​​bfs(); //bfs호출
​​​​}

​​​​//시작점을 변수로 받아 확인, 출력 후 다음 연결점을 찾아 시작점을 변경하여 재호출
​​​​public static void dfs(int i) {
​​​​​​​​checked[i] = true;
​​​​​​​​System.out.print(i + " ");

​​​​​​​​for (int j = 1; j <= n; j++) {
​​​​​​​​​​​​if (check[i][j] == 1 && checked[j] == false) {
​​​​​​​​​​​​​​​​dfs(j);
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}

​​​​public static void bfs() {
​​​​​​​​Queue<Integer> queue = new LinkedList<Integer>();
​​​​​​​​queue.offer(start); //시작점도 Queue에 넣어야 함
​​​​​​​​checked[start] = true;
​​​​​​​​System.out.print(start + " ");

​​​​​​​​//Queue가 빌 때까지 반복. 방문 정점은 확인, 출력 후 Queue에 넣어 순서대로 확인
​​​​​​​​while (!queue.isEmpty()) {
​​​​​​​​​​​​int temp = queue.poll();

​​​​​​​​​​​​for (int j = 1; j <= n; j++) {
​​​​​​​​​​​​​​​​if (check[temp][j] == 1 && checked[j] == false) {
​​​​​​​​​​​​​​​​​​​​queue.offer(j);
​​​​​​​​​​​​​​​​​​​​checked[j] = true;
​​​​​​​​​​​​​​​​​​​​System.out.print(j + " ");
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}
}

 

1. check / checked 배열

check = new int[1001][1001]; //좌표를 그대로 받아들이기 위해 +1해서 선언
checked = new boolean[1001]; //초기값 False

//간선 연결상태 저장
for (int i = 0; i < m; i++) {
​​​​​int x = sc.nextInt();
​​​​​int y = sc.nextInt();

​​​​​check[x][y] = check[y][x] = 1;
}

양방향 간선이기때문에 check[x][y] 와 check[y][x]는 같다.

 

이때, 좌표를 그대로 받아들이기 위해 +1해서 선언한다.

 

2. public static void dfs(int i)

​public static void dfs(int i) {
​​​​​​​​checked[i] = true;
​​​​​​​​//System.out.print(i + " ");

​​​​​​​​for (int j = 1; j <= n; j++) {
​​​​​​​​​​​​if (check[i][j] == 1 && checked[j] == false) {
​​​​​​​​​​​​​​​​dfs(j);//연결o, 방문x 이면 점점 깊숙히 호출
​​​​​​​​​​​​}
​​​​​​​​}
}

- 연결이 되어있는지 확인

- 방문하지 않은 노드인지 확인

 

3. public static void bfs()

public static void bfs() {
​​​​​​​​Queue<Integer> queue = new LinkedList<Integer>();
​​​​​​​​queue.offer(start); //시작점도 Queue에 넣어야 함
​​​​​​​​checked[start] = true;
​​​​​​​​//System.out.print(start + " ");

​​​​​​​​//Queue가 빌 때까지 반복. 방문 정점은 확인, 출력 후 Queue에 넣어 순서대로 확인
​​​​​​​​while (!queue.isEmpty()) {
​​​​​​​​​​​​int temp = queue.poll();

​​​​​​​​​​​​for (int j = 1; j <= n; j++) {
​​​​​​​​​​​​​​​​if (check[temp][j] == 1 && checked[j] == false) {
​​​​​​​​​​​​​​​​​​​​queue.offer(j);
​​​​​​​​​​​​​​​​​​​​checked[j] = true;
​​​​​​​​​​​​​​​​​​​​//System.out.print(j + " ");
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}
}

- Queue 구현 LinkedList 기반

- checked[start] = true 로 시작지점 방문 체크.

- 큐가 빌때까지 계속 큐에서 빼내서 작업

- 빼낸 노드에서 갈수있는 모든 노드들(연결o, 방문x)을 큐에 차례대로 넣고, 방문처리.