백준 - DFS와 BFS ( 1260번, JAVA )

DFS / BFS ( https://www.acmicpc.net/problem/1260 )

풀이

• 이제 DFS / BFS 문제를 피하지말자 🚀
• DFS 즉, 깊이우선 한놈만 판다라고 생각하자 보통 스택과 재귀함수를 활용해 푼다. 나는 재귀함수를 썼다.
• 시작점을 알려줬으니 start를 먼저 방문체크 / start에 연결된 정점을 찾아서 만약 방문하지 않았다면 그놈 또 들어간다. / 그 방문한 정점에서 연결된 놈이 또 방문한놈인지 체크한다. / 이렇게 하면 결국 마지막 foreach에서 전부 방문했기에 함수종료

• BFS 즉, 너비우선 이건 한놈과 관련된 모든놈들을 판다 라고 생각하자 먼저 start를 큐에 넣고 q의 최상단 정점에 해당하는 값을 빼준다. / 빼준 정점에 연결된 정점을 체크한다. / 만약 방문하지 않았다면 방문처리 후 q에 그 정점을 넣는다 / 이후 반복하면 결국 q는 비어있게 되면서 함수 종료

• DFS / BFS에 쫄지말자👍 모르겠다면 많은 문제를 보고 문제를 외워서라도 하자 🚀

package problem_solving.dfs_bfs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class BaekJoon_1260 {
	public static void dfs(int start, List<ArrayList<Integer>> graph, boolean[] visited) {

		visited[start] = true;
		StringBuilder sb = new StringBuilder();
		System.out.print(start+ " ");
		for(int num : graph.get(start)) {

			if( !visited[num]) {
				dfs(num, graph, visited);
			}

		}
	}




	public static void bfs(int start, List<ArrayList<Integer>> graph, boolean[] visited) {

		Queue<Integer> q = new LinkedList<Integer>();

		q.offer(start);
		visited[start] = true;
		StringBuilder sb = new StringBuilder();

		while(!q.isEmpty()) {
			int node = q.poll();

			sb.append(node+" ");

			for(int num : graph.get(node)) {

				if( !visited[num]) {
					visited[num] = true;
					q.offer(num);
				}
			}

		}
		System.out.println(sb.toString());

	}


	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int m = Integer.parseInt(sc.next());
		int v = Integer.parseInt(sc.next());

		List<ArrayList<Integer>> graph = new ArrayList<>();
		for(int i =0 ; i <= n ;i++) {
			graph.add(new ArrayList<>());
		}

		for(int i =0 ; i <m ; i++) {			
			int start = Integer.parseInt(sc.next());
			int end = Integer.parseInt(sc.next());
			graph.get(start).add(end);
			graph.get(end).add(start);

		}


		for(int i= 0 ; i < graph.size();i++) {			
			Collections.sort(graph.get(i));
		}


		boolean [] bfsVisited = new boolean[n+1];
		boolean [] dfsVisited = new boolean[n+1];



		dfs(v,graph, dfsVisited);
		System.out.println();
		bfs(v , graph, bfsVisited);


	}



}