백준 사이트

1

김학준님 안녕하세요 🙂

1. 맞아요 백준은 어떤 테스트 케이스에서 틀렸는지 알려주지 않기 때문에 어려운데, 그만큼 실전에 가까워서 실전 연습을 시켜주는데 도움이 되는 것 같아요. 초반에는 이렇게 하시는 게 어렵기 때문에 답을 알려주는 프로그래머스나 정올에서 풀어보시는 것도 좋은데, 어느 정도 문제에 익숙해져서 실전 모의고사를 하려면 백준을 추천드려요.

    

   그리고 백준에서 틀렸지만 왜 틀렸는지 모를 때는 여러 테스트 케이스를 만들어보며 확인하는 것도 연습해보시면 좋습니다. 결국 실제 시험 보러가셔서 테스트케이스가 정답이 안 나오거나, 간단한 건 통과했는데 제출하면 틀린 경우에 어떤 경우가 잘못됐는지 확인이 필요합니다.

이때 확인하는 방법은 주어진 테스트 케이스에서 값을 하나씩만 바꿔서 기존 답안에서 쉽게 계산할 수 있는 예제를 만들어야 해요. 안 그러면 내가 만든 테스트케이스를 계산하다가 시간을 다 낭비하게 됩니다. 그리고 테스트 케이스는 최대한 극단의 값을 확인하는 게 좋습니다. N이 1~ 1000 이 들어올 수 있다면 1과 1000, 0 과 1001 등 경계에 있는 테스트케이스에서 오동작하는 경우가 많습니다.

이런 식으로 문제가 될법한 테스트케이스를 빨리 찾는 것도 코딩테스트를 합격하는데 중요하니 백준에서 조금씩 연습해보셔도 좋을 것 같아요!

2. 제가 코드 답안을 따로 안 올렸네요! 우선 이 문제에 대한 답변은 지금 바로 올려드리고, 나머지는 이번 주 내로 답안 올려놓을게요! 조금만 기다려 주세요 🙂

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

class Main {
    final static int MAX = 1000000 + 10;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static int N, M, R;
    static int[] answer;
    static int order;

    public static void dfs(int idx) {
        visited[idx] = true;
        answer[idx] = order;
        order++;

        for(int i = 0; i < graph[idx].size(); i++)
            if (!visited[graph[idx].get(i)])
                dfs(graph[idx].get(i));
    }

    public static void main(String[] args) throws IOException{
        // 0. 입력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        
        // 1. graph에 연결 정보 채우기
        graph = new ArrayList[MAX];
        for(int i = 1; i <= N; i++)
            graph[i] = new ArrayList<>();
        visited = new boolean[MAX];
        answer = new int[MAX];
        order = 1;

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

        // 2. 오름차순 정렬
        for(int i = 1; i <= N; i++)
            Collections.sort(graph[i]);

        // 3. dfs(재귀함수 호출)
        dfs(R);

        // 4. 출력
        for(int i = 1; i <=N; i++){
            bw.write(String.valueOf(answer[i]));
            bw.newLine();
        }
        
        bw.close();
        br.close();
    }
}