백준 1260번 자바

문제

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

1260번: DFS와 BFS

 

1. BFS?

이 문제는 DFS, BFS에 대한 이해가 있어야 풀 수 있다.

DFS에 대한 간략한 설명은 아래에 링크를 첨부했다.

https://ahlight.tistory.com/82

백준 11724번 자바

 

- BFS : 넓이우선탐색(주로 Queue를 활용해 구현한다.)

- FIFO 탐색(선입선출)

- 현재 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘(최단,최소에 유용)

위 그림의 숫자 순서대로 탐색한다. 

현재 노드와 간선으로 이어진 인접노드를 먼저 방문 -> DFS

이전 노드와 간선으로 이어진 가까운 노드를 먼저 방문 -> BFS

가깝다와 인접의 의미가 다소 헷갈리는데 위 그림을 예로 설명하면 2번 노드를 현재 노드로 설정할 경우 의미가 명확해진다. 

DFS의 경우 2번이 현재 노드이고 그것과 간선으로 이어진 노드는 4와 5이다.

BFS의 경우 1번이 이전 노드이고 그것과 간선으로 이어진 노드는 2와 3이다. 2번은 현재 노드이기에 제외할 경우 3으로 탐색을 진행하고 같은 경우의 수가 여러개일 경우 3이후로 순차적으로 탐색을 한다.

 

2. 구현

DFS와 BFS를 기본적으로 구현할 수 있는지를 물어보는 문제다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main1260 {

	static int N,M,V;
	static List<Integer>[] arr;
	static List<Integer> dfsList = new ArrayList<Integer>();
	static List<Integer> bfsList = new ArrayList<Integer>();
	static boolean[] visited;
	
	public static void main(String[] args) throws IOException {
		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 ArrayList[N];
		visited = new boolean[N];
		
		for (int i=0; i<N; i++) {
			arr[i] = new ArrayList<Integer>();
		}
		
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a-1].add(b-1);
			arr[b-1].add(a-1);
		}
		
		for (int i=0; i<N; i++) {
			Collections.sort(arr[i]);
		}
		dfs(V-1);
		visited = new boolean[N];
		bfs(V-1);
		
		for (int i=0; i<dfsList.size(); i++) {
			System.out.print(dfsList.get(i)+1 + " ");
		}
		System.out.println();
		for (int i=0; i<bfsList.size(); i++) {
			System.out.print(bfsList.get(i)+1 + " ");
		}
	}
	
	public static void dfs(int node) {
		dfsList.add(node);
		visited[node] = true;
		for (int i=0; i<arr[node].size(); i++) {
			if (!visited[arr[node].get(i)]) {
				dfs(arr[node].get(i));
			}
		}
	}
	
	public static void bfs(int node) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(node);
		
		while (!q.isEmpty()) {
			int temp = q.poll();
			visited[temp] = true; // 아래와 중복. 첫 시작때문에 썼는데 그럴려면 while문 위로 빼는게 좋다.
			bfsList.add(temp);
			
			for (int i=0; i<arr[temp].size(); i++) {
				if (!visited[arr[temp].get(i)]) {
					visited[arr[temp].get(i)] = true;
					q.add(arr[temp].get(i));
				}
			}
		}
	}
}

 

정리 : 이번 문제에선 수의 범위가 넓지 않아 DFS,BFS를 실행한 값을 List에 저장했는데 만약 범위가 더 큰 수로 늘어난다면 StringBuilder를 활용해 출력하는게 시간단축에 더 유리할듯하다.