[백준] DFS와 BFS - 1260번 DFS와 BFS java

문제

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

1260번: DFS와 BFS

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

풀이

DFS와 BFS의 기초를 익힐 수 있는 문제다.

DFS란, 깊이 우선 탐색으로  하나의 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 한 방향으로 계속 진행하다가 더 이상 진행할 수 없을 때 가장 가까운 갈림길로 돌아와 이곳부터 다른 방향으로 다시 탐색을 진행하는 방법이다. 이는 재귀나 스택을 이용하여 풀이한다.

BFS란, 너비 우선 탐색으로 하나의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다. 이는 Queue를 이용하여 풀이한다.

왼쪽 : BFS / 오른쪽 : DFS

 

코드

package DFS와BFS;

import java.util.*;
import java.io.*;
public class No1260_DFS와BFS {
	
	static int[][] map; //간선 연결 상태 
	static boolean[] visited; //방문여부 
	static int n; //정점개수 
	static int m; //간선개수 
	static int start; //시작정점 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		start=sc.nextInt();
		
		map=new int[1001][1001];
		visited=new boolean[1001];
		
		//간선 연결 상태 입력 	
		for(int i=0;i<m;i++) {
			int x=sc.nextInt();
			int y=sc.nextInt();
			
			map[x][y]=map[y][x]=1;
		}
		
		//dfs
		dfs(start);
		
		visited=new boolean[1001]; //초기화 
		System.out.println();
		
		//bfs
		bfs();
	}
	
	static void dfs(int i){
		visited[i]=true;
		System.out.print(i+" ");
		
		for(int j=1;j<=n;j++) {
			if(map[i][j]==1&&!visited[j]) {
				dfs(j);
			}
		}
	}
	
	static void bfs() {
		Queue<Integer>q=new LinkedList<>();
		q.offer(start); //시작점 큐에 삽입 
		visited[start]=true;
		System.out.print(start+" ");
		
		while(!q.isEmpty()) {
			int tmp=q.poll();
			
			for(int j=1;j<=n;j++) {
				if(map[tmp][j]==1&&!visited[j]) {
					q.offer(j);
					visited[j]=true;
					System.out.print(j+" ");
				}
			}
		}
	}
}