1260번) DFS와 BFS

문제 출처 : https://www.acmicpc.net/problem/1260

기본 깊이우선 탐색 구현과 너비우선 탐색 구현입니다.

처음 구현하면서 학습한 블로그 주소 남깁니다. -> http://mygumi.tistory.com/102

import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Q1260 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int V = sc.nextInt(); int[][] A = new int[N][N]; for ( int i = 0; i < M; i++ ) { int start = sc.nextInt(); int goal = sc.nextInt(); A[start-1][goal-1] = 1; A[goal-1][start-1] = 1; } dfsSearch(A, new boolean[N], V-1); System.out.println(); bfsSearch(A, V-1); } public static void dfsSearch(int[][] A, boolean[] check, int now) { check[now] = true; System.out.print((now+1) + " "); for ( int i = 0; i < A.length; i++ ) { if ( now != i && A[now][i] != 0 && !check[i] ) { //자기 자신도 아니고, 가는길이 있으며, 가지 않은 길이면 dfsSearch(A, check, i); } } } public static void bfsSearch(int[][] A, int now) { boolean[] check = new boolean[A.length]; Queue<Integer> queue = new LinkedList<Integer>(); queue.add(now); while ( !queue.isEmpty() ) { now = queue.poll(); check[now] = true; System.out.print((now+1) + " "); for ( int i = 0; i < A.length; i++ ) { if ( now != i && A[now][i] != 0 && !check[i] ) { //자기 자신도 아니고, 가는길이 있으며, 가지 않은 길이면 queue.add(i); check[i] = true; } } } } }

오랜만에 BFS하려니 빡세네요??

2018년 4월 9일 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Q1260 { static int size, vSize; static int[][] values; public static void main(String[] args) { Scanner sc = new Scanner(System.in); size = sc.nextInt(); values = new int[size][size]; vSize = sc.nextInt(); int startNum = sc.nextInt()-1; for (int i = 0; i < vSize; i++) { int start = sc.nextInt()-1; int end = sc.nextInt()-1; values[start][end] = 1; values[end][start] = 1; } searchDfs(startNum, new boolean[size]); System.out.println(); searchBfs(startNum, new boolean[size]); } static void searchDfs(int startNum, boolean[] isVisit) { isVisit[startNum] = true; System.out.print(startNum+1 + " "); for (int i = 0; i < size; i++) { if (i != startNum && values[startNum][i] == 1 && !isVisit[i]) { searchDfs(i, isVisit); } } } static void searchBfs(int startNum, boolean[] isVisit) { Queue<Integer> queue = new LinkedList<Integer>(); queue.add(startNum); isVisit[startNum] = true; while(queue.size() > 0) { startNum = queue.poll(); System.out.print(startNum+1 + " "); for (int i = 0; i < size; i++) { if (i != startNum && values[startNum][i] == 1 && !isVisit[i]) { queue.add(i); isVisit[i] = true; } } } } }