백준 24479 문제 제출 결과 "틀렸습니다" 라고만 나와서 어떤... - 인프런

[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편

알고리즘 수업 - 깊이 우선 탐색 1 (백준 24479)

백준 24479 문제 제출 결과 "틀렸습니다" 라고만 나와서 어떤 부분이 틀렸는지 잘 모르겠어요 피드백 부탁드립니다

해결된 질문

작성

package com.study.book.graph;

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

public class Baekjoon24479 {

    private static ArrayList<Integer>[] adjList;
    private static boolean[] visited;
    private static int[] answer;
    private static int visitOrder;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        adjList = new ArrayList[N + 1];
        for (int i = 0; i < adjList.length; i++) {
            adjList[i] = new ArrayList<>();
        }

        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            adjList[x].add(y);
            adjList[y].add(x);
        }

        for (ArrayList<Integer> list : adjList) {
            Collections.sort(list);
        }

        visited = new boolean[N + 1];
        answer = new int[N + 1];
        visitOrder = R;

        dfs(R);

        for (int i = 1; i <= N; i++) {
            bw.write(String.valueOf(answer[i]));
            bw.newLine();
        }

        br.close();
        bw.close();
    }

    private static void dfs(int now) {
        visited[now] = true;
        answer[now] = visitOrder;
        visitOrder++;

        for (int next : adjList[now]) {
            if (!visited[next]) {
                dfs(next);
            }
        }
    }
}

안녕하세요 개취님!

알고리즘 강의 잘 듣고 있습니다 ㅎㅎ

다름이 아니라, 위 코드로 문제를 풀고 테스트 코드 또한 정상적으로 통과하여 백준에서 제출을 진행했는데, 단순히 "틀렸습니다" 라고만 나와서 어떤 점에서 문제가 있는지 정상적으로 파악이 안되서 문의드립니다!

한번 확인 후 피드백 주시면 감사하겠습니다.

java 코딩-테스트 알고리즘 dfs

답변 3

개발자로 취직하기

지식공유자

AI 인턴보다 한 발 늦었지만 두 가지 수정하면 될 것 같습니다!

엣지 읽기 루프:
- 엣지를 읽는 루프가 1부터 N + 1까지 반복되는데, M개의 엣지를 읽어야 합니다. 현재 구현은 N이 M보다 크면 필요한 것보다 더 많은 엣지를 읽을 수 있습니다!
방문 순서 초기화:
- 방문 순서(visitOrder)가 시작 노드 R로 초기화됩니다. 방문 순서는 1부터 시작하되, 첫 노드 번호를 R로 초기화 하도록 수정하면 정답이 될 것 같습니다 🙂

이재민

질문자

답변 감사합니다

인접리스트 초기화할때, 간선의 개수 만큼 반복문 선언, visitOrder의 초기화 실수, br 출력시 1번째 인덱스로 변경하니 정답 처리가 되네요

힌트 주셔서 감사합니다

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

널 포인터 에러 질문에 대한 답변을 참고하시면 도움이 될 수 있습니다. 버럼님의 경우 Java에서 그래프 관련 DFS 알고리즘을 구현했을 때 널 포인터 예외가 발생하는 문제를 겪었습니다. 버럼님의 예시 코드와 유사하게, 이재민님의 경우도 adjList 배열의 각 요소를 올바르게 초기화했는지, 그리고 dfs 함수를 실행하며 answer 배열의 인덱싱이 올바르게 처리되었는지 검토할 필요가 있습니다.

다만, 질문과 비교하여 직접적인 연관성을 파악하기에는 자세한 문제의 맥락이나 특정 에러 메시지에 대한 정보가 부족합니다. dfs 구현 과정에서 주요한 포인트는 모든 노드를 올바르게 방문 처리하는 것과 visitOrder를 적절하게 할당하는 것입니다. 구현한 dfs 함수 내에서 방문 순서를 대입하는 로직(answer[now] = visitOrder;)에 주목해야 합니다. 제시된 코드에서 visitOrder 변수는 시작 노드 R의 값으로 초기화되어 있으나, 문제의 요구사항에 따라 방문 순서를 나타내기 위한 초기값 설정이 올바른지 확인해야 합니다. 일반적으로 방문 순서를 나타내기 위한 변수는 1부터 시작하는 것이 일반적입니다.

위의 질문에서는 스택 오버플로우 또는 잘못된 인덱스 접근으로 인한 오류 등 다른 원인에 대한 가능성도 고려해야 하기 때문에, 구체적인 실행 오류나 다른 테스트 케이스에서의 실패 사례를 제공받지 못한 경우, 코드의 로직을 다시 한 번 세밀하게 검토할 것을 권장합니다.

현재 답변은 일반적인 DFS 구현 시 발생할 수 있는 문제와 기본적인 접근 방법에 대한 안내로 제한됩니다. 상세한 테스트 케이스나 구체적인 백준의 오류 메시지를 제공받지 못하였기 때문에, 다른 테스트 케이스에서의 문제점 또는 백준 사이트 특유의 문제 요구 사항에 대해 명확히 답변하기 어려운 점 양해 부탁드립니다. 🙏

추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

백준 24479 문제 제출 결과 "틀렸습니다" 라고만 나와서 어떤 부분이 틀렸는지 잘 모르겠어요 피드백 부탁드립니다