[백준] 1260번: DFS와 BFS

문제링크 : https://www.acmicpc.net/problem/1260

 

문제풀이

DFS는 보통 재귀 또는 스택을 이용해 풀고, BFS는 큐를 이용하여 구현한다.

이차원 배열로 두 정점이 연결되어 있는지 간선 정보를 저장해놓는다.

 

DFS : https://manzoo.tistory.com/69

[Algorithm] Depth-first-search (깊이 우선 탐색)

BFS : https://manzoo.tistory.com/12?category=767113

[Algorithm] Breadth-first search (너비 우선 탐색)

 

 

소스코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.util.Queue;

public class p_1260 {
	static int map[][];
	static boolean visit[];
	static int N;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s);

		N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int V = Integer.parseInt(st.nextToken());
		
		map = new int[N+1][N+1];
		visit = new boolean[N+1];
		
		for (int i = 0; i <= N; i++) {
			Arrays.fill(map[i], 0);
		}
		
		Arrays.fill(visit, false);
		
		for (int i = 0; i < M; i++) {
			String edge = br.readLine();
			st = new StringTokenizer(edge);

			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			
			map[v1][v2] = map[v2][v1] = 1;
		}

		dfs(V);
		System.out.println();
		Arrays.fill(visit, false);
		bfs(V);
	}
	
	public static void bfs(int v) {
		Queue queue = new LinkedList();
		queue.offer(v);
		visit[v] = true;
		System.out.printf(v + " ");
		while (!queue.isEmpty()) {
			int poll = queue.poll();
			for (int i = 1; i <= N; i++) {
				if (map[poll][i] == 1 && !visit[i]) {
					queue.offer(i);
					visit[i] = true;
					System.out.printf(i + " ");
				}
			}
		}
		for (int i = 1; i <= N; i++) {
			if (map[v][i] == 1 && !visit[i]) {
				bfs(i);
			}
		}
	}
	
	public static void dfs(int v) {
		visit[v] = true;
		System.out.printf(v + " ");
		for (int i = 1; i <= N; i++) {
			if (map[v][i] == 1 && !visit[i]) {
				dfs(i);
			}
		}
	}
}