글 읽기 - C#) 어디서 틀렸는지 감이 안잡힙니다. + 시도해 본 케이스들

paraworld 3년 전 13

BFS로 집합의 수(나눠진 지역구의 수)를 찾고, 백트래킹으로 탐색하는 식으로 짰습니다만, 어떤 케이스에서 틀리는지 모르겠습니다.

게시판 반례는 다 맞았습니다.

정 답이 안나오면 코드 밀고 다시 짜야할 것 같은데, 유니온 파인드를 이 문제에서 사용할 수 있는지도 궁금하네요.

아래는 만들어서 넣어본 케이스들입니다.

3
2 4 8
2 2 3
2 1 3
2 1 2

답 2 (1, 2 / 3)

4
2 4 8 16
2 2 3
2 1 3
2 1 2
0

답 2 (1, 2, 3 / 4)

2
1 3
1 2
1 1

답 2

5
1 3 2 4 5
1 3
3 5 4 3
2 1 2
1 2
1 2

답 5 (1, 2, 3, 4 / 5)

3
1 1 3
1 3
1 3
2 2 1

답 3

2
1 10
0
0
답 9

3
1 10 100
1 2
1 1
0

답 89

4
2 4 8 16
3 2 3 4
3 1 3 4
3 1 2 4
3 3 2 1

답 2 (1, 2, 3 / 4)

9
1 2 3 4 5 6 7 8 9
2 2 4
4 1 3 5 4
4 2 5 8 7
4 6 9 1 2
2 2 3
1 4
1 3
1 3
1 4

답 1 (3, 5, 7, 8 / 1, 2, 4, 6, 9)

9
1 2 3 4 5 6 7 8 9
8 2 3 4 5 6 7 8 9
8 1 3 4 5 6 7 8 9
8 2 1 4 5 6 7 8 9
8 2 3 1 5 6 7 8 9
8 2 3 4 1 6 7 8 9
8 2 3 4 5 1 7 8 9
8 2 3 4 5 6 1 8 9
8 2 3 4 5 6 7 1 9
8 2 3 4 5 6 7 8 1

답 1

9
1 2 3 4 5 6 7 8 9
3 5 6 8
3 5 7 9
3 4 5 8
3 3 5 9
8 1 2 3 4 6 7 8 9
3 1 5 7
3 2 5 6
3 1 3 5
3 2 4 5

답 1

10
43 21 32 4 54 9 12 35 76 81
3 5 6 8
3 5 7 9
4 4 5 8 10
3 3 5 9
8 1 2 3 4 6 7 8 9
3 1 5 7
3 2 5 6
3 1 3 5
3 2 4 5
1 3

답 15

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

// CapitalLetters for class names and methods, camelCase for variable names.
// Write your code clearly enough so that it doesn't need to be commented, or at least, so that it rarely needs to be commented.

namespace Testpad
{
    public class BaekJoon17471
    {
        static Dictionary<int, bool>[] lines; // 인접 리스트
        static int n; // 구역의 수

        static void Main()
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            n = int.Parse(sr.ReadLine()); // 구역의 수
            int[] population = sr.ReadLine().Split().Select(int.Parse).ToArray(); // 구역별 인구수

            int locSum = population.Sum(); // 모든 구역의 인구수 합
            int minDifferance = locSum; // 인구수 차이의 최소치

            lines = new Dictionary<int, bool>[n]; // 인접 리스트
            for (int i = 0; i < n; i++)
            {
                lines[i] = new Dictionary<int, bool>();
            }

            // 간선들의 정보를 받음
            for (int i = 0; i < n; i++)
            {
                int[] inputs = sr.ReadLine().Split().Select(int.Parse).ToArray();

                for (int j = 1; j < inputs.Length; j++)
                {
                    lines[i].Add(inputs[j] - 1, false);
                }
            }

            // 두 선거구로 나눌 수 있는지부터 확인
            int divided = DivideCheck(0, 1, new bool[n]);

            // 1개 선거구로 나눠지는 경우, 백트래킹으로 확인
            if (divided == 1)
            {
                Stack<int> stack = new Stack<int>();
                bool[,] used = new bool[n, n]; // 방문 체크
                bool[] inStack = new bool[n]; // 스택에 특정값이 있는지 여부

                for (int i = 0; i < n; i++)
                {
                    int thisResult = 0; // 현재 구역의 인구수 합

                    // 첫 원소를 스택에 추가
                    stack.Push(i);
                    used[0, i] = true;
                    thisResult += population[i];
                    inStack[i] = true;

                    // Console.WriteLine($"i = {i}, divCheck = {DivideCheck(i, 1, (bool[])inStack.Clone())}, result = {Math.Abs(locSum - thisResult * 2)}, stackCount = {stack.Count}"); // 디버그용

                    if (DivideCheck(i, 1, (bool[])inStack.Clone()) == 2) // 깊은 복사로 구현 안하면 형식만 복사됨
                    {
                        minDifferance = Math.Min(minDifferance, Math.Abs(locSum - thisResult * 2));
                    }

                    while (stack.Count > 0)
                    {
                        bool found = false; // 적당한 값을 찾았는지 여부
                     
                        if (stack.Count < n - 1) // 스택 크기가 n이면 집합이 1개가 되어서 의미가 없음
                        {
                            foreach (var item in lines[stack.Peek()])
                            {
                                if (used[stack.Count, item.Key] == false && inStack[item.Key] == false)
                                {
                                    used[stack.Count, item.Key] = true;
                                    inStack[item.Key] = true;
                                    thisResult += population[item.Key];
                                    stack.Push(item.Key);
                                    found = true;

                                    if (DivideCheck(i, 1, (bool[])inStack.Clone()) == 2) // 깊은 복사로 구현 안하면 형식만 복사됨
                                    {
                                        /*Console.WriteLine($"i = {i}, divCheck = {DivideCheck(i, 1, (bool[])inStack.Clone())}, result = {Math.Abs(locSum - thisResult * 2)}, stackCount = {stack.Count}"); // 디버그용
                                        foreach (var item1 in stack)
                                        {
                                            Console.WriteLine(population[item1] + " ");
                                        }*/

                                        minDifferance = Math.Min(minDifferance, Math.Abs(locSum - thisResult * 2));
                                    }

                                    if (stack.Count >= n - 1)
                                    {
                                        break;
                                    }
                                }
                            }
                        }

                        if (found == false)
                        {
                            for (int j = 0; j < n; j++)
                            {
                                used[stack.Count, j] = false;
                            }

                            inStack[stack.Peek()] = false;
                            thisResult -= population[stack.Peek()];
                            stack.Pop();
                        }
                    }
                }
            }
            // 정확히 2개 선거구로 나눠지는 경우, BFS 한번 돌려서 인구수 차이를 확인
            else if (divided == 2)
            {
                Queue<int> queue = new Queue<int>();
                bool[] used = new bool[n];

                queue.Enqueue(0);
                used[0] = true;
                int thisPopulation = population[0];

                while (queue.Count > 0)
                {
                    int thisTime = queue.Count;

                    for (int i = 0; i < thisTime; i++)
                    {
                        foreach (var item in lines[queue.Peek()])
                        {
                            if (used[item.Key] == false)
                            {
                                used[item.Key] = true;
                                queue.Enqueue(item.Key);
                                thisPopulation += population[item.Key];
                            }
                        }

                        queue.Dequeue();
                    }
                }

                minDifferance = locSum - thisPopulation * 2;
            }
            // 두 선거구로 나눌 수 없는 경우
            else
            {
                minDifferance = -1;
            }

            // 결과 출력
            sw.Write(minDifferance);

            sr.Close();
            sw.Close();
        }

        // 나눠지는 집합의 수를 구하는 연산
        // unionCount = 나눠진 집합의 수
        static int DivideCheck(int start, int unionCount, bool[] used)
        {
            Queue<int> queue = new Queue<int>();

            if (used[start] == false)
            {
                queue.Enqueue(start);
                used[start] = true;
            }

            while (queue.Count > 0)
            {
                int thisTime = queue.Count;

                for (int i = 0; i < thisTime; i++)
                {
                    foreach (var item in lines[queue.Peek()])
                    {
                        if (used[item.Key] == false)
                        {
                            used[item.Key] = true;
                            queue.Enqueue(item.Key);
                        }
                    }

                    queue.Dequeue();
                }
            }

            // 2개 이상의 집합으로 나눠지는 경우, BFS 한번 더돌려서 체크
            for (int i = 0; i < n; i++)
            {
                if (used[i] == false && unionCount <= 2)
                {
                    return DivideCheck(i, unionCount + 1, used);
                }
            }

            return unionCount;
        }
    }
}

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

문제

문제

출처

ICPC

C#) 어디서 틀렸는지 감이 안잡힙니다. + 시도해 본 케이스들

paraworld 3년 전 13

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말