글 읽기 - 반례가 있을까요...

ksm7558k 2년 전 0

어디서 틀린건지 못찾겠습니다 ㅠ

public class Main{
    public static void main(String[] args) {
        int answer = 0;
        int n;
        int line;
        int a, b;
        Scanner sc = new Scanner(System.<i>in</i>);

        n = sc.nextInt();
        line = sc.nextInt();
        boolean[][] arr = new boolean[n + 1][n + 1];
        for (int i = 0; i < line; i++) {
            a = sc.nextInt();
            b = sc.nextInt();
            arr[a][b] = true;
            arr[b][a] = true;
        }

        boolean[] road = new boolean[n + 1];
        road[1] = true;
        int idx = 1;

        while (idx <= n) {
            for (int i = 2; i <= n; i++) {
                if (arr[idx][i]) {
                    if (road[idx]) {
                        road[i] = true;
                        continue;
                    }
                }
                if (arr[i][idx]) {
                    if (road[i]) {
                        road[idx] = true;
                    }
                }
            }
            idx++;
        }

        for (boolean f : road) {
            if (f) {
                answer++;
            }
        }
        answer--;
        System.<i>out</i>.println(answer);
    }
}

fccva 2년 전 1

그래프 탐색 알고리즘을 한 번 찾아보세요.

인덱스 순서대로 찾으면 아래 같은 반례가 생기고

연결된 것에서 그 다음 연결된 것으로 찾아나가야합니다.

5
4
1 4
4 5
5 2
2 3
    
answer: 4
output: 3

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

문제

문제

출처

ICPC

반례가 있을까요...

ksm7558k 2년 전 0

fccva 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말