[BFS,DFS 연습] BOJ_1260 DFS와 BFS (S2)

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

1260번: DFS와 BFS

 

 

1. 전체 코드 (라이브 다시듣기 DFS(2) 활용)

 

package algo1004.DFSBFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_1260_DFS와BFS2 {

	// 0인덱스 이후인 1부터 사용하려고 배열 크기를 모두 + 1
	public static int N; // 정점의 갯수
	public static int M; // 간선의 갯수
	public static int V; // 탐색을 시작할 정점 번호
	public static boolean[][] map;

	public static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		st = new StringTokenizer(br.readLine(), " "); // 공백을 기준으로 문자열 분리
		N = Integer.parseInt(st.nextToken()); // 정점의 갯수를 저장
		M = Integer.parseInt(st.nextToken()); // 간선의 갯수를 저장
		V = Integer.parseInt(st.nextToken()); // 탐색을 시작할 정점 번호를 저장

		map = new boolean[N + 1][N + 1]; // 정점의 갯수 크기만큼 2차원배열 map 생성
		for (int i = 0; i < M; i++) { // 간선의 갯수만큼 반복문
			st = new StringTokenizer(br.readLine(), " "); // 공백을 기준으로 문자열 분리
			int from = Integer.parseInt(st.nextToken()); // 간선의 시작 노드
			int to = Integer.parseInt(st.nextToken()); // 간선의 끝 노드
			map[from][to] = map[to][from] = true; // 무향그래프이므로 대칭적으로 true 저장
		}

		// map 상태 확인
		//for (int j = 0; j < map.length; j++) {
		//	System.out.println(Arrays.toString(map[j]));
		//}

		boolean[] visit_dfs = new boolean[N + 1]; // dfs에서 쓸 boolean 배열 선언
		dfs(V, visit_dfs); // 깊이우선탐색 시작 (시작노드와 boolean배열 받음)
		sb.append("\n");
		bfs(); // 너비우선탐색 시작
		System.out.println(sb.toString());
	}

	private static void dfs(int current, boolean[] visit) {

		visit[current] = true; // 시작노드 방문체크
		sb.append(current + " "); // 시작노드 출력버퍼에 저장

		for (int i = 1; i < N + 1; i++) { // 1부터 N까지 탐색하면서
			if (!visit[i] && map[current][i]) { // 방문 안했거나, 간선이 존재하면
				dfs(i, visit); // 재귀
			}
		}
	}

	private static void bfs() {

		Queue<Integer> queue = new LinkedList<Integer>(); // 정점과 정점의 순서를 관리할 큐 선언
		boolean[] visit_bfs = new boolean[N + 1]; // 정점의 갯수만큼 중복에서 정점을 탐색하지 않도록 방문을 확인하는 배열 선언

		queue.offer(V); // 시작 정점 큐에 저장
		visit_bfs[V] = true; // 방문 표시

		while (!queue.isEmpty()) { // 큐가 비어있지 않으면 (비어있으면 함수 종료)
			int current = queue.poll(); // 현재 정점 인덱스를 저장

			sb.append(current + " ");
			for (int i = 1; i < N + 1; i++) {
				// 미방문 상태이면서 간선이 존재하면
				if (!visit_bfs[i] && map[current][i]) {
					queue.offer(i); // 해당 정점 큐에 저장
					visit_bfs[i] = true; // 방문 표시
				}
			}
		}
	}
}

 

 

2. 부분 코드

 

2-1. main 기억해야 할 포인트들

1) map[from][to] = map[to][from] = true; // 무향그래프이므로 대칭적으로 true 저장

2) boolean[] visit_dfs = new boolean[N + 1]; // dfs에서 쓸 boolean 배열 선언

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		st = new StringTokenizer(br.readLine(), " "); // 공백을 기준으로 문자열 분리
		N = Integer.parseInt(st.nextToken()); // 정점의 갯수를 저장
		M = Integer.parseInt(st.nextToken()); // 간선의 갯수를 저장
		V = Integer.parseInt(st.nextToken()); // 탐색을 시작할 정점 번호를 저장

		map = new boolean[N + 1][N + 1]; // 정점의 갯수 크기만큼 2차원배열 map 생성
		for (int i = 0; i < M; i++) { // 간선의 갯수만큼 반복문
			st = new StringTokenizer(br.readLine(), " "); // 공백을 기준으로 문자열 분리
			int from = Integer.parseInt(st.nextToken()); // 간선의 시작 노드
			int to = Integer.parseInt(st.nextToken()); // 간선의 끝 노드
			map[from][to] = map[to][from] = true; // 무향그래프이므로 대칭적으로 true 저장
		}

		// map 상태 확인
		//for (int j = 0; j < map.length; j++) {
		//	System.out.println(Arrays.toString(map[j]));
		//}

		boolean[] visit_dfs = new boolean[N + 1]; // dfs에서 쓸 boolean 배열 선언
		dfs(V, visit_dfs); // 깊이우선탐색 시작 (시작노드와 boolean배열 받음)
		sb.append("\n");
		bfs(); // 너비우선탐색 시작
		System.out.println(sb.toString());
	}

 

2-2. dfs 기억해야 할 포인트들

DFS : 방문관리, 재귀 사용

1) visit[current] = true; // 시작노드 방문체크 및 출력 (체크 시점이 함수 시작하자마자)

2) if (!visit[i] && map[current][i]) { // 방문 안했거나, 간선이 존재하면 (재귀호출 조건)

	private static void dfs(int current, boolean[] visit) {

		visit[current] = true; // 시작노드 방문체크
		sb.append(current + " "); // 시작노드 출력버퍼에 저장

		for (int i = 1; i < N + 1; i++) { // 1부터 N까지 탐색하면서
			if (!visit[i] && map[current][i]) { // 방문 안했거나, 간선이 존재하면
				dfs(i, visit); // 재귀
			}
		}
	}

 

2-3. bfs 기억해야 할 포인트들

BFS : 방문관리, 큐 사용

1) queue.offer(V); // 시작 정점 큐에 저장
    visit_bfs[V] = true; // 방문 표시

    => 시작노드 작업 : 큐에 저장, 방문 표시

2) while (!queue.isEmpty()) { // 큐가 비어있지 않으면 (비어있으면 함수 종료)
           int current = queue.poll(); // 현재 정점 인덱스를 저장
           sb.append(current + " ");

    => 큐에 현재 정점 인덱스 저장, 출력

3) if (!visit_bfs[i] && map[current][i]) {
           queue.offer(i); // 해당 정점 큐에 저장
           visit_bfs[i] = true; // 방문 표시

   => 조건을 만족하면 큐에 해당 노드 저장, 방문 표시

	private static void bfs() {

		Queue<Integer> queue = new LinkedList<Integer>(); // 정점과 정점의 순서를 관리할 큐 선언
		boolean[] visit_bfs = new boolean[N + 1]; // 정점의 갯수만큼 중복에서 정점을 탐색하지 않도록 방문을 확인하는 배열 선언

		queue.offer(V); // 시작 정점 큐에 저장
		visit_bfs[V] = true; // 방문 표시

		while (!queue.isEmpty()) { // 큐가 비어있지 않으면 (비어있으면 함수 종료)
			int current = queue.poll(); // 현재 정점 인덱스를 저장

			sb.append(current + " ");
			for (int i = 1; i < N + 1; i++) {
				// 미방문 상태이면서 간선이 존재하면
				if (!visit_bfs[i] && map[current][i]) {
					queue.offer(i); // 해당 정점 큐에 저장
					visit_bfs[i] = true; // 방문 표시
				}
			}
		}
	}