[BaekJoon] #1260 DFS와 BFS

문제이해

변형없이 베이직하게 BFS DFS 구현하는 문제입니다.
개념 복기하기 좋은 문제.

입력

입력으로 정점의 수, 간선의 수, 시작노드를 입력받고 간선정보가 주어집니다.

문제접근

1. BFS DFS에서 기본인 그래프를 linkedList 으로 표현해줍니다.
2. 해당 문제에서의 그래프는 양방향 그래프이고, 정점번호가 작은것먼저 방문하므로, 엣지를 추가해줄때 대칭적으로 추가해주고, 각 정점에 대한 리스트를 오름차순 정렬해주면 됩니다.
3. 구현해놓은 BFS DFS함수를 호출해주면 됩니다.

code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main{
    static boolean[] visited;
    static LinkedList<Integer>[] adjList;
    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.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            adjList = new LinkedList[n+1];
            for(int i=1; i<n+1; i++){
                adjList[i] = new LinkedList<Integer>();
            }
            for(int i=0 ; i<m; i++){
                st = new StringTokenizer(br.readLine());
                int v1 = Integer.parseInt(st.nextToken());
                int v2 = Integer.parseInt(st.nextToken());
                adjList[v1].add(v2);
                adjList[v2].add(v1);
            }
            for(int i=1; i<n+1; i++){
                Collections.sort(adjList[i]);
            }

            visited = new boolean[n+1];
            DFS(v);
            System.out.println();
            visited = new boolean[n+1];
            BFS(v);
    }
    private static void BFS(int v) {
      
        Queue<Integer> q = new LinkedList<>();
        visited[v] = true;
        q.add(v); 
        
        while(!q.isEmpty()){
            int nowNode = q.poll();
            System.out.print(nowNode+" ");
            for(int t : adjList[nowNode]){
                if(visited[t] != true){
                    visited[t]= true;
                    q.add(t);
                }
            }
        }
    }
    public static void DFS(int v){
        visited[v] = true;
        System.out.print(v+" ");
        for(int t : adjList[v]){
            if(!visited[t]){
                DFS(t);

            }
        }

    }
}