글 읽기 - 왜 틀린지를 모르겠습니다. ㅜㅜㅜ

sesdesa 5년 전 0

질문 게시판에 나오는 반례들도 다 넣어봤는데 올바른 답이 나오는데 왜 틀렸다고 하는지 모르겟어요 ㅜㅜ

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    static int count = 0;

    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        boolean[] visited = new boolean[N+1];
        LinkedList[] list = new LinkedList[N + 1];
        for(int i = 0; i <= N; i++){
            list[i] = new LinkedList<Integer>();
        }

        for(int i = 0; i < M; i++){
            int src = scan.nextInt();
            int dest = scan.nextInt();
            list[src].addLast(dest);
        }

        dfs(list, 1, visited);
        System.out.println(count);
    }

    static void dfs(LinkedList[] list, int start, boolean[] visited){

        if(visited[start] == true){
            count -= 1;
            return;
        }

        if(list[start].size() == 0){
            return;
        }

        visited[start] = true;
        int length = list[start].size();
        for(int i = 0; i < length; i++){
            dfs(list, Integer.parseInt(list[start].removeFirst().toString()), visited);
            count += 1;
        }       if(list[start].size() != 0){
            System.out.println(start + " -> " + list[start].peekFirst());
        }
    }
}

unilep 5년 전 1

System.out.println(start + " -> " + list[start].peekFirst());

sesdesa 5년 전 0

아 이럴수가....감사합니다...!!!

sesdesa 5년 전 0

음 저걸 지워도 틀렸다고 뜨네요 ㅜㅜㅜ 대체 어디가 문제일까요 ㅠ

unilep 5년 전 1

간선을 앙방향으로 하시고

if(visited[start] == true){
count -= 1;
return;
}

는 필요없을거같고

방문안된 node만 방문하도록 해보세용

아 그리고 List를 지우고있으신거같은데 제대로 작동할지는 모르겠습니다;

sesdesa 5년 전 0

감사합니다. 지적해주신 것과 양방향에 대한 고려를 해주지 않아서 그랬던 것 같습니다. 감사합니다!

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int count = 0;

    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        boolean[] visited = new boolean[N+1];
        List[] list = new ArrayList[N + 1];
        for(int i = 0; i <= N; i++){
            list[i] = new ArrayList<Integer>();
        }

        for(int i = 0; i < M; i++){
            int src = scan.nextInt();
            int dest = scan.nextInt();
            list[src].add(dest);
            list[dest].add(src);
        }

        dfs(list, 1, visited);
        System.out.println(count - 1);
    }

    static void dfs(List[] list, int start, boolean[] visited){

        if(visited[start] == true){
            return;
        }

        visited[start] = true;
        count += 1;
        int length = list[start].size();
        for(int i = 0; i < length; i++){
            dfs(list, Integer.parseInt(list[start].get(i).toString()), visited);
        }
    }
}

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

문제

문제

출처

ICPC

왜 틀린지를 모르겠습니다. ㅜㅜㅜ

sesdesa 5년 전 0

unilep 5년 전 1

sesdesa 5년 전 0

sesdesa 5년 전 0

unilep 5년 전 1

sesdesa 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말