[JAVA] 1260번 DFS와 BFS

[JAVA] 1260번 DFS와 BFS

문제

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

풀이

dfs와 bfs의 탐색 결과에 따라 방문순서를 출력하는 문제이다.

dfs의 경우 재귀로 문제를 풀었고, bfs는 큐를 사용해 해결하였다.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class DFS와BFS { static int N, M, V; static boolean arr[][]; static boolean visited[]; public static void DFS(int start) { visited[start] = true; System.out.print(start + " "); for (int i = 0; i < N + 1; i++) { if (arr[start][i] && !visited[i]) { DFS(i); } } } public static void BFS(int start) { Queue q = new LinkedList<>(); visited[start] = true; q.offer(start); while(!q.isEmpty()) { int v = q.poll(); System.out.print(v + " "); for (int i = 0; i < N + 1; i++) { if (arr[v][i] && !visited[i]) { q.offer(i); visited[i] = true; } } } System.out.println(); } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); V = Integer.parseInt(st.nextToken()); arr = new boolean[N+1][N+1]; visited = new boolean[N+1]; for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int start = Integer.parseInt(st.nextToken()); int end = Integer.parseInt(st.nextToken()); arr[start][end] = true; arr[end][start] = true; } DFS(V); System.out.println(); visited = new boolean[N+1]; BFS(V); } }

from http://pekahblog.tistory.com/152 by ccl(S) rewrite - 2021-09-21 05:27:51