DFS/BFS - DFS와 BFS

이번 문제는 백준 알고리즘 사이트에 문제입니다.

DFS와 BFS 관련 문제로 기본/핵심 적인 문제입니다.

문제

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

분석/설계

제목 부터과 DFS/BFS 이여서 당연히 DFS/BFS로 접근하였습니다.

기본적인 DFS/BFS 구현과 유사하지만 두 정점 사이에 여러개의 간선과 양방향 이라는 점에서 주의해야합니다.

처음에 양방향을 생각하지 않고 풀이 했을대, 예제 1번은 답이 나왔지만 2,3 번은 모두 오답이 었습니다. 

구현 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class DFSBFS {

	static boolean[] visted;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	
	public static void dfs(int V) {
		visted[V] = true;
		System.out.print(V + " ");
		
		for(int i=0; i<graph.get(V).size(); i++) {
			int W = graph.get(V).get(i);
			if(!visted[W]) dfs(W);	
		}
	}
	
	public static void bfs(int V) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(V);
		
		visted[V] = true;
		
		while(!queue.isEmpty()) {
			int x = queue.poll();
			System.out.print(x + " ");
			for(int i=0; i<graph.get(x).size(); i++) {
				int W = graph.get(x).get(i);
				if(!visted[W]) {
					queue.offer(W);
					visted[W] = true;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int N = scanner.nextInt(); // 정점의 개수
		int M = scanner.nextInt(); // 간선 열결하는 두 정점의5 번호
		int V = scanner.nextInt(); // 시작할 정점 번호
		
		for(int i=0; i<=N; i++) { // 인접 배열 리스트 초기화
			graph.add(new ArrayList<Integer>());
		}
		
		visted = new boolean[N+1]; // 방문 여부 판단할 배열
		
		scanner.nextLine();
		for(int i=0; i<M; i++) { // 인접 배열 리스트 값 세팅 
			int v1 = scanner.nextInt();
			int v2 = scanner.nextInt();
			graph.get(v1).add(v2); 
			graph.get(v2).add(v1);
		}
		
		for(int i=1;i<=N;i++) { // 이동 간선의 이동 경우가 다수 존재할 경우 작은 정점부터 이동해야하므로 오름차순 정렬
			Collections.sort(graph.get(i));
		}
		
		dfs(V);
		visted = new boolean[N+1]; // dfs 수행 후 방문 여부 판단할 배열 초기화
		System.out.println();
		bfs(V);
		scanner.close();
	}
}

 

정리

DFS 재귀 함수로 BFS는 Queue를 이용해서 구현했다.

기본적인 그래프에 대한 DFS/BFS 를 구현하는 문제였고 사소한 구현 사항을 놓치지 않으면

쉽게 풀수 있는 문제입니다. 

 

참고

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