글 읽기 - 1260번 왜 틀린 건가요??;; 잘 모르겠습니다.

bulgogi1216 5년 전 0

트리 검색 DFS-스택, BFS-큐 로 구현했는데 왜 틀린건가요;;

import java.util.*;

public class Main {
    static class Graph {
        int V; //Number of Vertices

        public LinkedList<Integer>[] adj; // adjacency lists

        //Constructor
        Graph(int V) {
            this.V = V;
            adj = new LinkedList[V];

            for (int i = 0; i < adj.length; i++)
                adj[i] = new LinkedList<Integer>();

        }

        //To add an edge to graph
        void addEdge(int v, int w) {
            adj[v].add(w); // Add w to v’s list.
        }

        // prints all not yet visited vertices reachable from s
        void DFS(int s) {
            // Initially mark all vertices as not visited
            Vector<Boolean> visited = new Vector<Boolean>(V);
            for (int i = 0; i < V; i++)
                visited.add(false);

            // Create a stack for DFS
            Stack<Integer> stack = new Stack<>();

            // Push the current source node
            stack.push(s);

            while (stack.empty() == false) {
                // Pop a vertex from stack and print it
                s = stack.peek();
                stack.pop();

                // Stack may contain same vertex twice. So
                // we need to print the popped item only
                // if it is not visited.
                if (visited.get(s) == false) {
                    System.out.print(s + " ");
                    visited.set(s, true);
                }

                // Get all adjacent vertices of the popped vertex s
                // If a adjacent has not been visited, then puah it
                // to the stack.
                Iterator<Integer> itr = adj[s].descendingIterator();

                while (itr.hasNext()) {
                    int v = itr.next();
                    if (!visited.get(v))
                        stack.push(v);
                }

            }
        }

        // prints BFS traversal from a given source s
        void BFS(int s) {
            boolean visited[] = new boolean[V];

            LinkedList<Integer> queue = new LinkedList<>();

            visited[s]=true;
            queue.add(s);

            while (queue.size() != 0)
            {
                s = queue.poll();
                System.out.print(s+" ");

                // Get all adjacent vertices of the dequeued vertex s
                // If a adjacent has not been visited, then mark it
                // visited and enqueue it
                Iterator<Integer> i = adj[s].listIterator();
                while (i.hasNext())
                {
                    int n = i.next();
                    if (!visited[n])
                    {
                        visited[n] = true;
                        queue.add(n);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String tmpStr = sc.nextLine();
        String[] tmp = tmpStr.split(" ");

        int N = Integer.valueOf(tmp[0]);
        int M = Integer.valueOf(tmp[1]);
        int startNode = Integer.valueOf(tmp[2]);

        Graph g = new Graph(N + 1);
        for (int i = 0; i < M; ++i) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            g.addEdge(from, to);
        }

        sc.close();
        g.DFS(startNode);
        System.out.println();
        g.BFS(startNode);
    }
}

djm03178 5년 전 0

질문글을 쓸 때 위에 나오는 공지사항을 읽으면 다음과 같은 말이 있습니다.

"질문 검색을 먼저 해서 자신에게 필요한 답변이나 반례가 없는지 확인하고 질문을 남겨주세요."

https://www.acmicpc.net/board/... 이렇게 좋은 반례 모음집이 있습니다.

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

문제

문제

출처

ICPC

1260번 왜 틀린 건가요??;; 잘 모르겠습니다.

bulgogi1216 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말