BFS - 18352

문제 설명

1. 입력 첫번째 줄로 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시 번호 X가 주어짐
2. 두번째 줄부터 M개의 줄로 A B의 형태로 A->B로 가는 간선 정보가 주어짐
3. X로부터 최단 거리가 K인 모든 도시의 번호를 오름차순으로 출력, 없는 경우 -1 출력

문제 풀이

이전과 동일하게 bfs 알고리즘의 문제이다. 따라서 Queue 자료형과 방문기록을 위한 코드를 사용했다. 

아래는 최종 코드다.

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

namespace StudyCS
{
    class Program
    {
        public class Vertex
        {
            public Vertex()
            {
                canMoveVertex = new List<int>();
            }
            private List<int> canMoveVertex;

            public void AddVertex(int inVertex)
            {
                canMoveVertex.Add(inVertex);
            }
            public bool FindVertex(int inVertex)
            {
                if(canMoveVertex.Contains(inVertex))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            public List<int> GetCanMoveVertex()
            {
                return canMoveVertex;
            }
            public int GetCanMoveVertexCount()
            {
                return canMoveVertex.Count;
            }
        }
        public static void Main(string[] args)
        {
            //입력 처리
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int N = input[0]; //도시의 갯수
            int M = input[1]; //도로의 갯수
            int K = input[2]; //거리 정보
            int X = input[3]-1; //출발 도시의 번호

            List<Vertex> vertices = new List<Vertex>();
            for(int i = 0; i < N; i++)
            {
                vertices.Add(new Vertex());
            }
            for(int i = 0; i < M; i++)
            {
                input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                int A = input[0]; //도로의 출발 도시 번호
                int B = input[1]; //도로의 도착 도시 번호
                vertices[A-1].AddVertex(B-1);
            }

            Queue<int> queue = new Queue<int>();
            queue.Enqueue(X);
            int[] distance = new int[N];
            for(int i = 0; i < N; i++)
            {
                distance[i] = -1;
            }
            distance[X] = 0;

            List<int> result = new List<int>(); //거리가 K인 정점을 기록하는 자료형
            while (queue.Count > 0)
            {
                int targetVertex = queue.Dequeue();
                //Console.WriteLine($"Target Vertex : {targetVertex}");
                foreach (int neighborVertex in vertices[targetVertex].GetCanMoveVertex())
                {
                    if(distance[neighborVertex] == -1)
                    {
                        queue.Enqueue(neighborVertex);
                        distance[neighborVertex] = distance[targetVertex] + 1;
                    }
                }
            }
            for (int i = 0; i < N; i++)
            {
                if(distance[i] == K)
                {
                    result.Add(i);
                }
            }
            if (result.Count < 1)
            {
                Console.WriteLine(-1);
                return;
            }
            result.Sort();
            for (int i = 0; i < result.Count; i++)
            {
                Console.WriteLine(result[i]+1);
            }
        }
    }
}

코드 설명

코드에서의 특이한 점은 정점의 번호를 인덱스로 바꾸기 위해 -1을 했다는 점이다.

따라서 출력에서도 인덱스 +1을 하여 정점의 번호를 출력해야 한다.

 

코드가 완성되고 난 후에는 괜찮았지만 많은 시행 착오를 거쳤다.

시행착오는 아래와 같다

시행착오

1. Vertex의 자료형을 bool[,]로 설정해서 필요 없는 부분의 자료까지 저장하여 N*N의 크기로 최대 30만 * 30만의 크기를 가져 메모리 초과 오류가 떴다.
2. 따라서 필요한 부분만큼만 저장하기 위해 List<Tupe<int, int>>자료형으로 바꾸어 사용하였다. 하지만 이 방법은 메모리는 효율적이지만 시간적인 측면에서 이웃 간선이 아닌 리스트의 모든 튜플을 확인해야하므로 비효율적으로 시간 초과가 발생했다.
3. 이후 인접 간선 정보와 방문 정보를 저장하기 위해 Vertex Struct를 만들어 그 안에 List<int>형으로 인접 간선 목록과 bool형으로 visited를 만들었다. 하지만 Struct 타입은 Value Type으로 Deep Copy가 일어나 새로운 Struct를 생성해 visited의 원본 값이 안바뀌는 현상이 발생하였다.
4. 따라서 Reference Type인 Class로 전환하여 참조 형식으로 Shallow Copy가 일어나 주소값을 복사하여 원본 값이 바뀌게 되었다.
5. 하지만 지금 코드에서는 struct의 외부로 방문목록인 bool형의 visited를 빼서 class와 struct가 크게 차이가 나지 않는다. struct가 복사가 되더라도 한번에 하나만 복사가 되기 때문에 반복문이 한 번 반복될때마다 하나의 복사본이 생성되고 바로 삭제되기 때문이다. 

예전에 깊은 복사(Deep Copy)와 얕은 복사(Shallow Copy)에 대해서 공부했지만 언어마다 조금씩 달라서 공부해야할 것 같다.

C#과 Cpp의 Struct 자료형 차이점

• Cpp
  • 값형(Value Type)과 참조형(Reference Type)이 둘 다 가능하다.
  • 두 개를 구분하는 조건은 stack과 heap 중 어느 부분에 할당이 되느냐의 차이다.
• C#
  • 값형(Value Type)이다.
  • 복사할 때는 내부에 있는 타입에 따라서 얕은 복사를 하거나 깊은 복사를 한다.
  • 위의 경우에서는 struct 객체를 복사한 후 안에 있는 List<int>는 얕은 복사를 하고 bool은 깊은 복사를 하게 된다.

cpp에서의 struct는 값형과 참조형 둘 다 가능한 자료형으로 주로 참조형으로 선언하여 포인터를 사용해 신경을 안쓰다보니 이런 현상이 벌어지게 된 것 같다. C#에서 Struct를 사용할 때는 값이 변하지 않는 자료들을 주로 다루며 조심하면서 사용하도록 하자.