[BOJ] 1260. DFS와 BFS

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

1260번: DFS와 BFS

---

접근 방법

제목 값 하는 문제이다. stack을 이용한 DFS 방식과 queue를 이용한 BFS 방식으로 풀었다.

DFS는 2023.05.18 - [Baekjun] - 2606. 바이러스 

BFS는

(1) 시작 노드 queue 삽입 & 방문 처리

(2) 탐색 노스 queue 삽입

(3) queue 빌 때까지 최근 삽입한 노드부터 조회 & 인접 노드 존재 false

(4) visited를 통해 방문 X 인접 노드 존재하면, queue  삽입 & 방문 처리 & 인접 노드 존재 true

(5) 방문 X 인접 노드 존재하지 않으면, 이미 같은 층에서 다른 노드도 탐색하고 있으므로 아무 처리하지 않는다.

 

소스 코드

import java.util.*;
import java.io.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.valueOf(st.nextToken());
		int M = Integer.valueOf(st.nextToken());
		int V = Integer.valueOf(st.nextToken());
		
		ArrayList<Integer>[] g = new ArrayList[N+1];
		
		for(int i=0; i<=N; i++) {
			g[i] = new ArrayList<>();
		}
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.valueOf(st.nextToken());
			int m = Integer.valueOf(st.nextToken());
			g[n].add(m);
			g[m].add(n);
		}	
		
		for(int i=0; i<=N; i++) {
			Collections.sort(g[i]);
		}
		
		DFS(g, V, N);
		sb.append("\n");
		BFS(g, V, N);
		
		System.out.println(sb.toString());
	}
	
	static void DFS(ArrayList<Integer>[] g, int root, int n) { // FILO
		boolean[] visited = new boolean[n+1];
		Arrays.fill(visited, false);

		Stack<Integer> s = new Stack<>();
		s.push(root);
		visited[root] = true;
		sb.append(String.valueOf(root) + " ");
		
		while(!s.isEmpty()) {
			int nn = s.peek();
			boolean hasNode = false;
			
			for(int i: g[nn]) {
				if (!visited[i]) {
					hasNode = true;
					s.push(i);
					visited[i] = true;
					sb.append(String.valueOf(i) + " ");
					break;
				}
			}
			if(hasNode == false)
				s.pop();
		}
	}
	static void BFS(ArrayList<Integer>[] g, int root, int n) { // FIFO
		boolean[] visited = new boolean[n+1];
		Arrays.fill(visited, false);
        
		Queue<Integer> q = new LinkedList<>();
		q.add(root);
		visited[root] = true;
        
		while(!q.isEmpty()) {
			int nn = q.poll();
			sb.append(String.valueOf(nn) + " ");
			
			for(int i: g[nn]) {
				if (!visited[i]) {
					q.add(i);
					visited[i] = true;
				}
			}
		}
	}
}