백준 1260 다시 풀어보기

이전 풀이
https://girokeulhaja.tistory.com/89

[Algorithm] 99클럽 코테 스터디 6일차 TIL | 백준_DFS와 BFS(1260번)

 

한 달 전에 풀어본 문제를 다시 풀어보았다.

풀고 나니 같은 사람이 푼 문제가 맞나 싶을 정도로 코드가 훨씬 깔끔해졌다는 생각이 든다!

메모리와 시간 모두 이전보다 절약해서 풀기도 하여 뿌듯함에 기록해본다.🫠

 

ArrayList를 정렬하는 방법이 Collections.sort()임을 기억하자,,,

 

전체 풀이

import java.util.*;
import java.io.*;
class Main{
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    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.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());
        graph = new ArrayList[N+1];
        for(int i = 0; i <= N; i++){
            graph[i] = new ArrayList<>();
        }
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }
        for(int i = 0; i <= N; i++){
            Collections.sort(graph[i]);
        }
        visited = new boolean[N+1];
        dfs(V);
        sb.append("\n");
        visited = new boolean[N+1];
        bfs(V);
        System.out.println(sb);
    }
    public static void dfs(int v){
        visited[v] = true;
        sb.append(v).append(" ");
        for(int n : graph[v]){
            if(!visited[n]){
                dfs(n);
            }
        }
    }
    public static void bfs(int v){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);
        visited[v] = true;
        while(!queue.isEmpty()){
            int q = queue.poll();
            sb.append(q).append(" ");
            for(int n : graph[q]){
                if(!visited[n]){
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}