[Condingame] DEATH FIRST SEARCH - EPISODE 1(탈출 차단하기 - 그래프, 너비 우선 탐색)

문제 간략 설명: 이 에피소드는 영화 <터미네이터>를 모티브로 해서 만들었습니다.

스카이넷 skynet은 터미네이터에서 인류의 적으로 나오는 인공지능 슈퍼컴퓨터입니다.

저항군은 스카이넷을 교란하기 위해 바이러스를 네트워크에 침투시키기 시작했습니다.

스카이넷은 이에 대응해서 에이전트를 보내 바이러스를 제거하려 합니다. 여러분은 저항군을 도와 바이러스가 에이전트에 의해 파괴되지 않도록 해야 합니다.

[사진]

[Rules_규칙]

목표: 문제 간략 설명에서 스카이넷이니... 바이러스니... 침투하니... 파괴되지 않게 하니...

이런 어려운 설명보다는 그냥 탈옥 영화를 보면 탈옥수가 감옥에서 탈옥하는데  탈옥수와 출구와의 최단 경로의 길목을 봉쇄한다고 생각하는 게 더 직관적입니다.

문제의 설명과는 다르지만 문제가 솔직히 너무 어렵게 설명합니다 ㅡ.ㅡ!

그래서 제가 문제 영상 보고 바로 떠오른 건 탈옥 영화였습니다.

 

[풀이 영상]

 

규칙: 

각 테스트 케이스마다 다음 정보가 제공됩니다.
- 네트워크 구성
- 출구의 위치(출구는 여러 존재할 수 있습니다)
- 스카이넷 에이전트의 위치
노드는 하나의 출구에만 연결됩니다(노드 1개에 여러 개의 출구가 연결되는 경우는 없습니다).

턴마다 게임은 다음 순서대로 진행됩니다.
- 여러분은 네트워크에서 노드 사이의 간선 하나를 끊습니다.
- 그 이후 스카이넷 에이전트는 이동 가능한 노드로 한 번 이동합니다.

Victory Conditions_승리 조건
스카이넷 에이전트가 출구에 도달할 수 없습니다.

Lose Conditions_패배 조건
- 스카이넷 에이전트가 출구에 도달합니다.
- 잘못된 값을 출력합니다.

Game Input_게임의 입력 및 출력 값
프로그램은 게임 시작 시 네트워크의 정보를 알려주는 초기 데이터와 매 턴 스카이넷 에이전트의 위치를 알려주는 데이터로 나누어져 있습니다. 

초기 데이터에는 네트워크의 노드 개수, 노드 간 연결 정보 및 출구의 개수와 위치를 알려줍니다. 

턴마다 스카이넷 에이전트의 위치를 읽고 연결을 끊을 두 노드를 출력해야 합니다.
-Initialization input_처음에 입력받는 초깃값
첫 번째 라인: 3개의 정수 N, L, E를 입력받습니다.
- N은 출구를 포함해서 전체 노드의 개수를 말합니다. 노드 번호는 0부터 N-1까지입니다.
- L은 노드 간 연결되어 있는 전체 간선의 개수를 말합니다.

- E는 출구의 개수를 말합니다.
다음 라인: 노드 간 연결을 알려줍니다. 각 라인은 2개의 정수 N1, N2로 이루어져 있습니
다. N1 노드와 N2 노드가 서로 연결되어 있다는 뜻입니다.
다음 E라인 출구 노드의 번호를 알려줍니다.

Input for one game turn_턴마다 입력받는 값
1개의 정수 SI(Skynet agent Index)를 입력받습니다. SI는 스카이넷 에이전트의 현재 위치를 알려주는 인덱스 번호입니다.

Output for one game turn_턴마다 출력해야 할 값
2개의 정수 C1 C2를 출력해야 합니다. C1과 C2는 공백으로 구분되어 있습니다.

이렇게 하면 C1과 C2 노드 사이의 연결이 끊어집니다.

잘못된 노드 번호를 출력하면 게임에서 패배합니다.

 

[문제]

 

https://www.codingame.com/training/medium/death-first-search-episode-1

Practice BFS and Graphs with the exercise "Death First Search - Episode 1"

 

[난이도]

[학습 개념]

[풀이]

1. Node 클래스

Node 클래스는 그래프의 노드를 표현하는 클래스입니다. 각 노드는 값을 가지고 있으며(Value), 방문 여부를 나타내는 플래그(Flag)를 가지고 있습니다(Visited). 또한 인접한 노드들의 리스트(Neighbors)도 관리합니다.

2. Graph 클래스

Graph 클래스는 그래프를 표현하고 그래프 관련 기능을 제공하는 클래스입니다. 이 클래스는 노드들을 저장하는 딕셔너리(Nodes)를 가지고 있습니다. AddNode 메서드는 새로운 노드를 추가하고, AddEdge 메서드는 두 노드 사이에 간선을 추가합니다. RemoveEdge 메서드는 두 노드 사이의 간선을 제거합니다. IsExitDisconnected 메서드는 주어진 출구 노드와 연결된 노드가 없는지 확인합니다. FindShortestPath 메서드는 시작 노드부터 목표 노드까지의 최단 경로를 찾아 반환합니다.

3. Player 클래스

Player 클래스는 게임 플레이어를 나타내는 클래스입니다. Main 메서드는 게임 루프를 실행합니다. 초기에는 그래프와 게임 정보를 초기화하고, 게임 루프에서는 현재 위치(SI)에서 출구까지의 최단 경로를 찾아 출력합니다. 그리고 출력한 간선을 제거하고, 출구와 연결된 노드가 없으면 출구 리스트에서 제거합니다.

이 코드는 그래프와 BFS 알고리즘을 활용하여 출구로 가는 최단 경로를 찾아 가장 마지막 노드와 마지막에서 두 번째 노드사이의 간선을 제거하고 출력하는 코드입니다.

BFS 알고리즘은 너비 우선 탐색을 통해 가까운 노드부터 순서대로 탐색하면서 최단 경로를 찾는 방식입니다. 이를 통해 게임 레벨에서 출구로 가는 최단 경로를 찾을 수 있습니다.

이 코드는 게임 개발에서 최단 경로 문제를 해결하는 데에 활용할 수 있습니다. 출구로 가는 최단 경로를 찾고, 해당 경로의 간선을 제거하여 게임의 진행을 조절할 수 있습니다. 이를 통해 게임 캐릭터나 에이전트가 최적의 경로를 선택하도록 할 수 있습니다.

이 코드의 핵심은 BFS 알고리즘을 사용하여 최단 경로를 찾는 부분입니다. BFS는 그래프 탐색 알고리즘 중 하나로, 시작 노드에서부터 차례로 인접한 노드를 방문하면서 최단 경로를 찾아갑니다. 이 알고리즘을 활용하여 게임 레벨에서 출구로 가는 최단 경로를 찾을 수 있습니다.

 

 

[소스 코드]

 

using System;
using System.Collections.Generic;

namespace myCode
{
    public class Node
    {
        public int Value { get; set; }
        public bool Visited { get; set; }
        public List<Node> Neighbors { get; set; }

        public Node(int value, bool visited)
        {
            Value = value;
            Visited = false;
            Neighbors = new List<Node>();
        }
    }

    public class Graph
    {
        public Dictionary<int, Node> Nodes { get; set; }  // 그래프의 노드들을 저장하는 딕셔너리

        public Graph()
        {
            Nodes = new Dictionary<int, Node>();
        }

        public void AddNode(int value)
        {
            Nodes.Add(value, new Node(value, false));  // 새로운 노드 추가
        }

        public void AddEdge(int from, int to)
        {
            Nodes[from].Neighbors.Add(Nodes[to]);  // 두 노드 사이에 간선 추가
            Nodes[to].Neighbors.Add(Nodes[from]);  // 양방향 그래프
        }

        public void RemoveEdge(int from, int to)
        {
            Nodes[from].Neighbors.Remove(Nodes[to]); // 두 노드 사이에 간선 제거
            Nodes[to].Neighbors.Remove(Nodes[from]);
        }

        public bool IsExitDisconnected(int exitNode) //출구와 연결된 노드가 다 끊겼는지 확인하는 함수
        {
            return Nodes[exitNode].Neighbors.Count == 0;
        }
        public List<int> FindShortestPath(int start, int goal)
        {
            Queue<Node> queue = new Queue<Node>();  // BFS에 사용할 큐 생성
            queue.Enqueue(Nodes[start]);  // 시작 노드 큐에 삽입
            Nodes[start].Visited = true;  // 시작 노드 방문 표시

            Dictionary<int, int> parent = new Dictionary<int, int>();  // 각 노드의 부모 노드를 저장하는 딕셔너리

            while (queue.Count > 0)
            {
                Node current = queue.Dequeue();  // 큐에서 노드 추출

                foreach (Node neighbor in current.Neighbors)  // 현재 노드의 인접한 노드들에 대해
                {
                    // 인접 노드가 방문하지 않은 경우
                    if (neighbor.Visited == false)
                    {
                        queue.Enqueue(neighbor);  // 인접 노드 큐에 삽입
                        Nodes[neighbor.Value].Visited = true;  // 인접 노드 방문 표시
                        parent[neighbor.Value] = current.Value;  // 부모 노드 저장
                    }
                }
            }

            // 최단 경로 구성
            List<int> path = new List<int>();
            int node = goal;
            while (node != start)
            {
                path.Insert(0, node);  // 경로의 시작점에 노드 삽입
                node = parent[node];  // 부모 노드로 이동
            }
            path.Insert(0, start);  // 시작점 삽입

            // 최단 경로를 보여주는 함수 호출
            ShortPathWrite(path);

            return path;  // 최단 경로 반환
        }

        public void ShortPathWrite(List<int> path)
        {
            Console.Error.Write($"최단 경로: ");
            for (int i = 0; i < path.Count - 1; i++)
            {
                Console.Error.Write($"{path[i]} -> ");
            }

            // 마지막 노드 출력
            Console.Error.WriteLine(path[path.Count - 1]);
        }
    }

    class Player
    {
        static void Main(string[] args)
        {
            Graph graph = new Graph();

            string[] inputs = Console.ReadLine().Split(' ');
            int N = int.Parse(inputs[0]); // the total number of nodes in the level, including the gateways
            int L = int.Parse(inputs[1]); // the number of links
            int E = int.Parse(inputs[2]); // the number of exit gateways

            for (int i = 0; i < N; i++)
            {
                graph.AddNode(i);
            }

            for (int i = 0; i < L; i++)
            {
                inputs = Console.ReadLine().Split(' ');
                int N1 = int.Parse(inputs[0]); // N1 and N2 defines a link between these nodes
                int N2 = int.Parse(inputs[1]);
                graph.AddEdge(N1, N2);
            }

            List<int> EI = new List<int>(); // the array of gateway node
            for (int i = 0; i < E; i++)
            {
                EI.Add(int.Parse(Console.ReadLine())); // the index of a gateway node
                
            }

            // game loop
            while (true)
            {
                int SI = int.Parse(Console.ReadLine()); // The index of the node on which the Bobnet agent is positioned this turn

                //출구가 여러개 일 때, 가장 짧은 경로를 찾아서 저장
                List<int> ShortestPath = null;
                foreach (int ei in EI)
                {
                    foreach (Node node in graph.Nodes.Values)
                    {
                        node.Visited = false;
                    }
                    var path = graph.FindShortestPath(SI, ei);
                    
                    if (ShortestPath == null || path.Count < ShortestPath.Count)
                    {
                        ShortestPath = path;
                    }
                }
                    
                int C1 = ShortestPath[ShortestPath.Count - 2];
                int C2 = ShortestPath[ShortestPath.Count - 1];
                Console.WriteLine($"{C1} {C2}");

                // 출력한 간선 제거
                graph.RemoveEdge(C1, C2);

                // 출구와 연결된 노드가 하나도 없으면 그 출구는 완전히 막혀있다고 판단
                // 고려 사항에서 제거
                if (graph.IsExitDisconnected(C2))
                {
                    EI.Remove(C2);
                }
            }
        }
    }
}

 

[새롭게 알게 된 점]

1. 노드 클래스를 그래프 클래스에서 사용하고 그 그래프 클래스를 통해 노드들을 관리하고 사용하는 방법을 통해 객체 사용법과 깔끔한 코드를 표현하기 위한 노력을 통해 코딩 실력이 향상됨을 느낌

2. BFS를 구현하면서 BFS와 DFS에 대한 구현에 자신감이 생김

3. 깊이 우선 탐색을 이용해 최단 경로를 찾을 수 없나? 하고 궁금해서 생각을 좀 해봤는데 모든 경로를 깊이 우선 탐색으로 전부 확인해서 비교하면 될 거 같아서 확인해 보니 너비 우선 탐색에 비해 메리트가 없어서 그냥 선조들이 괜히 넓이 우선 탐색으로는 최단 경로 찾기를 한 게 아님을 다시 한번 느낌.

깊이 우선 탐색의 장단점

• 장점:
  • 최선의 경우, 가장 빠른 알고리즘이다. ‘운 좋게’ 항상 해에 도달하는 올바른 경로를 선택한다면, 깊이 우선 탐색이 최소 실행시간에 해를 찾는다.
• 단점:
  • 찾은 해가 최적이 아닐 가능성이 있다.
  • 최악의 경우, 가능한 모든 경로를 탐험하고서야 해를 찾으므로, 해에 도달하는 데 가장 오랜 시간이 걸린다.

너비 우선 탐색의 장단점

• 장점:
  • 최적해를 찾음을 보장한다.
• 단점:
  • 최소 실행시간보다는 오래 걸린다는 것이 거의 확실하다.
  • 최악의 경우, 실행에 가장 긴 시간이 걸릴 수 있다.