글 읽기 - 1260 DFS/BFS 질문 드립니다.

ionmax5602 1년 전 0

88%에서 오류가 나는걸 보니 정답이 얼마 안남은것 같은데요 ㅠ

테스트케이스를 여러개 만들어서 넣어봤는데 작동은 잘 되는지라

어디서 문제가 생겼는지 도통 감이 안잡히네요..

답변 부탁드리겠습니다. 감사합니다!

import java.util.*;

public class Main {
    static HashMap<Integer, ArrayList<Integer>> edge = new HashMap<>();
    static HashMap<Integer, Boolean> visit = new HashMap<>();
    static HashMap<Integer, Boolean> check = new HashMap<>();
    static Queue<Integer> qu = new LinkedList<>();
    static ArrayList<Integer> quRes = new ArrayList<>();
    static ArrayList<Integer> stRes = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(), M = sc.nextInt(), V = sc.nextInt();

        for (int i = 0; i < M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            if (!edge.containsKey(a)) edge.put(a, new ArrayList<>());
            if (!edge.containsKey(b)) edge.put(b, new ArrayList<>());
            edge.get(a).add(b);
            edge.get(b).add(a);
        }

        for (int i : edge.keySet()) {
            Collections.sort(edge.get(i));
            visit.put(i, false);
            check.put(i, false);
        }

        dfs(V);

        for (int i : edge.keySet()) visit.put(i, false);    // dfs 끝나고 bfs를 위해 visit 데이터 초기화.

        bfs(V);

        for (int i : stRes)
            System.out.printf("%d ", i);
        System.out.println();
        for (int i : quRes)
            System.out.printf("%d ", i);

    }

    public static void dfs(int vertex) {
        visit.put(vertex, true);
        stRes.add(vertex);
        for (int i = 0; i < edge.get(vertex).size(); i++)
            for (int j : edge.get(vertex))
                if (!visit.get(j)) dfs(j);
    }

    public static void bfs(int vertex) {
        if(!check.get(vertex) && !visit.get(vertex)) {
            visit.put(vertex,true);
            check.put(vertex,true);
            qu.offer(vertex);
        }
        for(int i : edge.get(vertex))
            if(!check.get(i)) {
                qu.offer(i);
                check.put(i, true);
            }
        quRes.add(qu.poll());
        if(!qu.isEmpty())
            if(!visit.get(qu.peek())) {
                bfs(qu.peek());
            }
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1260 DFS/BFS 질문 드립니다.

ionmax5602 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말