[백준] DFS와 BFS 1260 java - dfs, bfs

dfs, bfs 개념만 알고 있으면 쉽게 풀 수 있는 문제다!

다만 처음에 문제를 잘못 이해해서 마지막 테스트케이스가 이상하게 출력됐다..

모든 정점을 다 방문했을 때에 dfs, bfs 종료되도록 코드를 구현했었는데

마지막 케이스 같은 경우에는 정점은 1000까지 있지만

연결된 정점 정보가 999,1000만 나오기 때문에 모든 정점이 다 주어진 것은 아니다.

 

따라서 종료 조건을 없애고, result를 배열에서 List로 자료구조를 변경했다 !

 

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

 

 

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

public class Main {
    static int N, M, V;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static ArrayList<Integer> result;
    static void dfs(int start, int cnt){
        for(int i=0;i<graph[start].size();i++){
            int value = graph[start].get(i);
            if(!visited[value]){
                result.add(value);
                visited[value] = true;
                dfs(value, cnt+1);
            }
        }
    }

    static void bfs(int start, int cnt){
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        result.add(V);
        visited[V] = true;

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

            for(int i=0;i<graph[now].size();i++){
                int value = graph[now].get(i);
                if(!visited[value]){
                    q.add(value);
                    result.add(value);
                    visited[value] = true;
                }
            }
        }
    }

    static void print(){
        for(int i=0;i<result.size();i++)
            System.out.print(result.get(i)+" ");
        System.out.println();
    }
    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());

            graph = new ArrayList[N+1];
            visited = new boolean[N+1];
            result = new ArrayList<>();
            for(int i=0;i<N+1;i++)
                graph[i] = new ArrayList<>();

            for(int i=0;i<M;i++){
                st = new StringTokenizer(br.readLine());
                int n1 = Integer.parseInt(st.nextToken());
                int n2 = Integer.parseInt(st.nextToken());
                graph[n1].add(n2);
                graph[n2].add(n1);
            }


            for(int i=1;i<N+1;i++){
                Collections.sort(graph[i]);
            }

            visited[V] = true;
            result.add(V);
            dfs(V, 0);
            print();

            visited = new boolean[N+1];
            result = new ArrayList<>();
            bfs(V,0);
            print();
    }
}