[JAVA]백준_1260_DFS와 BFS

문제링크

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

1260번: 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 Main {
	
	static int N,M,V;
	static List<Integer>[] list;
	static boolean isVisited[];
	static StringBuilder sb;
	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());
		
		list = new ArrayList[N+1];
		
		for(int i=1;i<N+1;i++) list[i] = new ArrayList<>();
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			
			list[from].add(to);
			list[to].add(from);
		}
		
		for(int i=1;i<N+1;i++) Collections.sort(list[i]);
		isVisited = new boolean[N+1];
		sb = new StringBuilder();
		sb.append(V+" ");
		dfs(V);
		System.out.println(sb);
		
		isVisited = new boolean[N+1];
		sb = new StringBuilder();
		sb.append(V+" ");
		bfs(V);
		System.out.println(sb);
		
	}
	
	static void dfs(int v) {
		isVisited[v] = true;
		
		int size = list[v].size();
		for(int i=0;i<size;i++) {
			int num = list[v].get(i);
	
			if(!isVisited[num]) {
				sb.append(num+" ");
				isVisited[num] = true;
				dfs(num);
				
			}
		}
	}
	
	static void bfs(int v) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(v);
		isVisited[v] = true;
		
		while(!q.isEmpty()) {
			int num = q.poll();
			
			int size = list[num].size();
			for(int i=0;i<size;i++) {
				int number = list[num].get(i);
				if(!isVisited[number]) {
					sb.append(number+" ");
					isVisited[number] = true;
					q.offer(number);
				}
			}
		}
	}

}

 

정점의 개수가 1000개 까지 가능하기 때문에 배열로 구현할 경우 1000*1000짜리 배열을 만들어야되서 힘들 것 같았다.

 

그래서 리스트로 그래프를 구현하였다.

리스트 배열에는 정점의 수가 들어가고 add를 통해 도착지점을 추가해주었다.

list[from].add(to) 라고 생각하시면 된다.

또한 DFS, BFS를 구현하기 위해 isVisited배열을 추가하여 방문한 곳은 재방문하는 일이 없도록 하였다.

 

DFS

 

DFS는 재귀적으로 돈다.

일단 현재 방문 정점 True로 해준 뒤 현재 방문 노드에 연결된 자식들을 살펴본다.

그 자식들이 방문하지 않은 정점이면 출력할 StringBuilder에 추가해주고 isVisited 배열도 true로 setting 해준 뒤

다시 dfs를 도는 형식이다.

 

 

BFS

BFS는 큐를 이용하여 구현하면 된다.

현재 방문 정점의 값을 큐에 삽입한 뒤 큐가 빌 때 까지 돌면서 확인해주면 된다.

밑의 부분은 DFS와 비슷하여 설명을 생략하겠다.