[ BOJ/C# ] 11724 연결 요소의 개수

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

BFS로 풀었다. 전의 BFS들보다 고려할 조건들이 많았다. 

제출을 보면 굉장히 많이 틀렸는데, 내가 간과했던 점들을 적어보았다. 

 

1. 런타임 에러  (IndexOutOfRange)

visited 배열 크기를 1000으로 설정 -> 1001로 바꾸고 해결

 

2. 간선이 존재하지 않는 정점들도 하나의 요소로 더해주어야 한다. 

마지막에 for문으로 해결

-이 부분은 처음에 의문이었다. 문제에 정점이 n개 주어졌을 때, 1부터 n 까지라는 조건이 없었기 때문이다. 

그렇기 때문에 n==3이라면 정점은 1, 5, 7이렇게도 주어질 수 있다고 생각하였다.

하지만 테스트케이스들을 보면 1, 2, 3과 같이 순차적으로 주어지기 때문에 이를 결과로 유추할 수 있었다. 

 

3. 간선이 아예 주어지지 않을 경우(m==0)

요소는 정점의 개수와 동일하다. 

 

4. 나머지는 자신의 조건식과 반례들을 비교하며 찾기

나의 경우에는 (visited[v] == 0)의 경우에 visited[u]를 고려하지 못한 식을 만들었기 때문에 틀렸다. 

+ 질문게시판을 보면 '무방향 그래프'라는 것을 간과하고 map을 한쪽만 추가해주는 실수도 많이 보았다. 

 

using System;

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

            int[] visited = new int[1001];
            int[] nm = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
            int count = 0;
            if (nm[1] == 0) count = nm[0];  //간선 존재 X
            else
            {
                int[,] map = new int[nm[0] + 1, nm[0] + 1];
                Queue<int> q = new Queue<int>();
                for (int i = 0; i < nm[1]; i++)
                {
                    int[] uv = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
                    map[uv[0], uv[1]] = 1;
                    map[uv[1], uv[0]] = 1;
                    q.Enqueue(uv[0]);
                }
                while (q.Count > 0)
                {
                    int u = q.Dequeue();
                    for (int v = 1; v <= nm[0]; v++)
                    {
                        if (map[u, v] == 1)
                        {
                            if (visited[v] == 0 && visited[u] == 0) count++;
                            visited[u] = 1;
                            visited[v] = 1;
                        }
                    }
                }
                //간선으로 존재하지 않는 정점을 하나의 요소로 더해주기
                for (int i = 1; i <= nm[0]; i++)
                    if (visited[i] == 0) count++;
            }
            sw.Write(count);
            sr.Close();
            sw.Flush();
            sw.Close();
        }
    }
}

 

반례가 많이 적혀있는 글

https://www.acmicpc.net/board/view/47059

글 읽기 - 연결요소개수 BFS풀이 반례 부탁드립니다.