글 읽기 - C#) 반례를 3번이나 찾아서 고쳤는데, 이제 모르겠습니다.

paraworld 3년 전 0

4195번 문제랑 비슷해서 해시를 사용한 유니온-파인드로 풀었는데, 어디서 잘못되었는지는 모르겠지만 틀렸답니다.

반례를 3번이나 찾아냈는데..

5
h:b.
f:c,d.
b:c,f.
c:e,o.
o:p.
7
a:b.
e:f.
f:g.
b:c,o.
d:e.
c:d.
g:h.
5
a:aa.
b:a,aa.
c:a,b,aa.
aa:qw,qq.
qq:qw.
0

답
3
2
1

여전히 틀렸다네요..

반례 더 찾아봐야 뭔가 근본적인 부분에서 문제가 있었으면 시간낭비일 테니, 더 찾는 것이 의미가 있을지 모르겠습니다.

이 문제를 유니온-파인드로 접근하는 것이 맞는지, 그렇다면 어디가 잘못되었는지 궁금합니다.

구글링해도 푼 사람이 적은 문제라서 그런지 풀이가 안나옵니다.

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

// 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
{
    // 3
    // h:t.
    // a:b,c,d.
    // b:c,f.
    // 0
    public class BaekJoon3865
    {
        static Dictionary<string, Dictionary<string, bool>> team = new Dictionary<string, Dictionary<string, bool>>(); // 팀들 정보
        static Dictionary<string, string> linkedTeams = new Dictionary<string, string>(); // 팀의 종속성

        // 유니온 파인드?..
        static void Main()  
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int n; // 팀의 수
            while ((n = int.Parse(sr.ReadLine())) != 0)
            {
                team.Clear();
                linkedTeams.Clear();

                // 주어지는 팀들을 받음
                for (int i = 0; i < n; i++)
                {
                    string[] inputs = sr.ReadLine().Split(':');
                    string teamName = inputs[0]; // 팀 이름
                    team.Add(teamName, new Dictionary<string, bool>());

                    // 회원들을 받음
                    inputs = inputs[1].Split(',');
                    inputs[inputs.Length - 1] = inputs[inputs.Length - 1].Replace(".", ""); // 마지막 회원에 있는 마침표 제거
                    foreach (var item in inputs)
                    {
                        team[teamName].Add(item, false);
                    }

                    linkedTeams.Add(teamName, teamName);
                }

                Dictionary<string, bool> used = new Dictionary<string, bool>(); // 사용한 이름들 목록

                // 첫 팀에 있는 회원 수를 구함
                int result = 0;
                foreach (var item in team[team.First().Key])
                {
                    if (team.ContainsKey(item.Key) == false)
                    {
                        if (used.ContainsKey(item.Key) == false)
                        {
                            used.Add(item.Key, false);
                            result++;
                        }
                    }
                }

                foreach (var teamName in team)
                {
                    if (team[teamName.Key].ContainsKey(team.First().Key) != true)
                    {
                        foreach (var item in team[teamName.Key])
                        {
                            // 다른 팀 이름인지 확인
                            if (team.ContainsKey(item.Key) == true)
                            {
                                // 다른 팀 이름인 경우, 해당 팀을 뒤져서 또 거기에 다른 팀 이름이 있는지 확인하는 걸 반복
                                // 사이클은 없다고 했으니, 무한루프는 안돌듯
                                Union(teamName.Key, item.Key);
                            }
                        }
                    }

                    Find(teamName.Key);
                }

                foreach (var teamName in linkedTeams)
                {
                    // Console.WriteLine($"main = {teamName.Key}, sub = {teamName.Value}"); // 디버그용

                    if (teamName.Value == team.First().Key)
                    {
                        foreach (var item in team[teamName.Key])
                        {
                            if (team.ContainsKey(item.Key) == false)
                            {
                                if (used.ContainsKey(item.Key) == false)
                                {
                                    used.Add(item.Key, false);
                                    result++;
                                }
                            }
                        }
                    }
                }

                sw.WriteLine(result);
            }

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

        static void Union(string a, string b)
        {
            a = Find(a);
            b = Find(b);

            if (a == b)
            {
                return;
            }

            linkedTeams[b] = a;
        }

        static string Find(string a)
        {
            if (linkedTeams[a] == a)
            {
                return linkedTeams[a];
            }
            else
            {
                linkedTeams[a] = Find(linkedTeams[a]);
                return linkedTeams[a];
            }
        }
    }
}

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

문제

문제

출처

ICPC

C#) 반례를 3번이나 찾아서 고쳤는데, 이제 모르겠습니다.

paraworld 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말