글 읽기 - 1953 팀배분 다른 사람 풀이랑 비슷한것 같은데 왜 틀렸다고 뜰까요?

techhanx 4년 전 0

다른 사람 풀이는 보니까 visit[i] = visit[now]*-1; 이렇게 하고 나중에 visit이 1과 -1인 것을 나눠서 팀으로 구성하던데

저는 toTeam1 이라는 boolean을 선언해서 그냥 번갈아가면서 넣어줬는데 왜 틀릴까요?

이 소스에서 다른 사람처럼 visit[i] = visit[now]*-1로 바꾸면 맞았다고 뜹니다...

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

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

        int studentNum = s.nextInt();
        s.nextLine();

        boolean[][] arr = new boolean[studentNum + 1][studentNum + 1];
        for (int i = 1; i < studentNum + 1; i++) {
            int hateNum = s.nextInt();
            for (int j = 0; j < hateNum; j++) {
                int hateTarget = s.nextInt();
                arr[i][hateTarget] = true;
                arr[hateTarget][i] = true;
            }
        }

        LinkedList<Integer> team1 = new LinkedList<>();
        LinkedList<Integer> team2 = new LinkedList<>();

        // 모든 노드에 bfs를 돌린다.
        LinkedList<Integer> q = new LinkedList<>();
        boolean[] visit = new boolean[studentNum + 1];
        for (int i = 1; i < studentNum + 1; i++) {
            if (visit[i]) {
                continue;
            }

            q.add(i);
            visit[i] = true;
            boolean toTeam1 = true;

            while (!q.isEmpty()) {
                int now = q.pop();

                // 번갈아가면서 넣는다.
                if (toTeam1) {
                    team1.add(now);
                } else {
                    team2.add(now);
                }
                toTeam1 = !toTeam1;

                for (int j = 1; j < studentNum + 1; j++) {
                    if (arr[now][j] && !visit[j]) {
                        q.add(j);
                        visit[j] = true;
                    }
                }
            }
        }

        System.out.println(team1.size());
        team1.stream().sorted().forEach(i -> System.out.print(i + " "));
        System.out.println();
        System.out.println(team2.size());
        team2.stream().sorted().forEach(i -> System.out.print(i + " "));
    }
}

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

문제

문제

출처

ICPC

1953 팀배분 다른 사람 풀이랑 비슷한것 같은데 왜 틀렸다고 뜰까요?

techhanx 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말