[BAEKJOON 백준] 1260 DFS와 BFS

acmicpc.net/problem/1260

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

위와 같이 입력과 간선을 통해서 배열을 만든다.

 

이 문제는 BFS와 DFS를 이용해서 답을 내야한다.

 

먼저 BFS는 LinkedList를 통해서 점을 찾아가는 방식으로 답을 만들었다.

 

그리고, DFS는 boolean을 이용해서 출력을 해주는 방식으로 문제를 풀었다.

import java.util.LinkedList;
import java.util.Scanner;

public class Main {

	static int N,arr[][];
	static boolean isSelected[];
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		
		N=sc.nextInt();
		arr=new int[N+1][N+1];

		isSelected=new boolean[N+1];
		int M=sc.nextInt();
		int start=sc.nextInt();
		LinkedList <Integer> que=new LinkedList<>();

		boolean visit[]=new boolean[N+1];
		for(int i=0;i<M;i++) {
			int f=sc.nextInt();
			int t=sc.nextInt();
			arr[f][t]=arr[t][f]=1;

		}
		DFS(start);
		System.out.println();
		que.offer(start);
		visit[start]=true;
		while(!que.isEmpty()) {
			int temp=que.poll();
			for(int i=1;i<=N;i++) {
				if(arr[temp][i]==1&&!visit[i]) {
					que.offer(i);
					visit[i]=true;
				}
			}
			System.out.print(temp+" ");
		}
	}

private static void DFS(int start) {
	isSelected[start]=true;
	System.out.print(start+" ");
	for(int i=1;i<=N;i++) {
		if(arr[start][i]==1&&!isSelected[i]) {
			
			DFS(i);
		}
		
	}
	
}
}