[알고리즘] 백준 1260번 DFS와 BFS 문제 풀이

[알고리즘] 백준 1260번 DFS와 BFS 문제 풀이

반응형

개요

알고리즘에 있어서 가장 기본이 된다고 할 수 있는 DFS와 BFS에 대한 이해가 중요하여 가장 기본문제 중 하나인 백준 1260번을 풀어봄.

문제

풀이

BFS (너비 우선 탐색)

- 큐로 구현함.

- 한 정점에서 다른 정점으로 갈 수 있는 경로를 다 넣고 탐색이 끝나면 그다음 큐에서 갈 수 있는 정점들을 탐색.

DFS (깊이 우선 탐색)

- 재귀 함수로 구현함.

- 한 정점에서 갈 수 있는 모든 경로들을 다 탐색함.

코드

import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class pro_1260 { public static int[][] map; public static boolean[] visited; public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int V = sc.nextInt(); map = new int[N+1][N+1]; // 초기 경로 셋팅 for(int i=0; i < M; i++) { int a = sc.nextInt(); int b = sc.nextInt(); map[a][b] = 1; map[b][a] = 1; } visited = new boolean[N+1]; DFS(V); System.out.println(); visited = new boolean[N+1]; BFS(V); } public static void DFS(int V) { visited[V] = true; System.out.print(V + " "); for(int i=1 ; i queue = new LinkedList<>(); queue.add(V); while(!queue.isEmpty()) { int temp = queue.peek(); queue.poll(); for(int i=1; i

결과

반응형

from http://jung-story.tistory.com/134 by ccl(A) rewrite - 2021-11-03 10:01:35