[BAEKJOON] 백준 25595: 86 ─에이티식스─ 2 (C#)

문제 링크

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

 

 

문제

 

기아데 연방 공화국은 '레기온'이라는 인공지능 무인 병기들과 전쟁 중이다. 공화국은 레기온에 대항할 수단으로 '레긴레이브'라는 보행 병기를 개발했다. 공화국 군인들 중 소수정예는 이 레긴레이브에 탑승해서 레기온에 맞서 싸운다.

신에이 노우젠은 제 86 전략기동전단 기갑전대의 전대장이자 근접전의 대가이다. 그는 레기온들의 위치를 전부 파악할 수 있는 이능력이 있다. 그의 전투 스타일은 직접 레기온이 있는 위치 근처로 가서 빠르게 해치우는 것이다. 레긴레이브는 화력이 다소 떨어지지만, 기동성이 뛰어나다는 장점이 있기 때문이다.

레긴레이브는 대각선 네 방향으로 이동할 수 있다. 현재 좌표가 (𝑟,𝑐)라면 (𝑟−1,𝑐−1), (𝑟−1,𝑐+1), (𝑟+1,𝑐−1), (𝑟+1,𝑐+1)로 움직일 수 있다. 그리고 대각선으로 이동할 때 이동 경로에 인접한 레기온을 최대 2기까지 해치울 수 있다. 각각의 이동 경우마다 해치울 수 있는 레기온 위치는 다음과 같다.

<레긴레이브 이동가능 좌표>

이동하려는 위치에 레기온이 있어도 겹쳐서 있을 수 있다. 다만, 겹친 위치에 있는 레기온은 해치울 수 없다.

기습받은 레기온들은 당황하여 모두 움직임을 멈춘 상태다. 레기온들의 위치가 주어졌을 때, 신에이 노우젠이 레기온을 모두 해치우는 게 가능한지 판단해보자.

신에이 노우젠은 전장을 벗어나 이동할 수는 없다.

 

 

입력

첫 번째 줄에 전장의 크기 𝑁이 주어진다. 전장은 𝑁×𝑁크기 좌표로 이루어져 있다. 다음 𝑁개의 줄에는 전장의 정보가 주어진다. 각 줄마다 𝑁개의 좌표 정보가 주어지며 0은 빈칸, 1은 레기온, 2는 신에이 노우젠의 현재 위치를 나타낸다.

•  1≤𝑁≤100
•  0≤레기온 개수 ≤𝑁2−1
• 신에이 노우젠의 위치는 유일하다.

 

 

출력

전장에 레기온이 없거나 모든 레기온을 해치울 수 있다면 첫 줄에 "Lena"를 출력하고, 아니라면 "Kiriya"를 출력한다.

 

 

 

통과한 답안

using System.Collections.Generic;

namespace _25595
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[,] matrix = new int[N, N];
            List<(int, int)> regions = new List<(int, int)>();
            (int x, int y) start = (-1, -1);


            for (int i = 0; i < N; i++)
            {
                string[] inputs = Console.ReadLine().Split(' ');
                for (int j = 0; j < N; j++)
                {
                    matrix[i, j] = int.Parse(inputs[j]);
                    if (matrix[i, j] == 2)
                    {
                        start = (i, j);
                    }
                    else if (matrix[i, j] == 1)
                    {
                        regions.Add((i, j));
                    }
                }
            }

            int[] dx = { -1, -1, 1, 1 };
            int[] dy = { -1, 1, -1, 1 };

            bool[,] visited = new bool[N, N];
            Queue<(int x, int y)> queue = new Queue<(int x, int y)>();
            queue.Enqueue(start);
            visited[start.x, start.y] = true;
            bool allCleared = true;

            while (queue.Count > 0)
            {
                var (x, y) = queue.Dequeue();
                for (int i = 0; i < 4; i++)
                {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    
                    if (IsInBounds(nx, ny, N) && matrix[nx, ny] == 1)
                    {
                        allCleared = false;
                        break;
                    }

                    if (IsInBounds(nx, ny, N) && !visited[nx, ny])
                    {
                        queue.Enqueue((nx, ny));
                        visited[nx, ny] = true;
                    }
                }

                if (!allCleared) break;
            }

            Console.WriteLine(allCleared ? "Lena" : "Kiriya");
        }

        static bool IsInBounds(int x, int y, int N)
        {
            return x >= 0 && x < N && y >= 0 && y < N;
        }
    }
}

 

2차원 좌표가 주어졌을 때, 주인공은 대각선으로만 이동할 수 있고,

이동하면서 좌우에 있는 적을 처치할 수 있다.

적이 1로 표시되고 주인공이 2로 표시되는 경우,

모든 적을 처치할 수 있는지를 묻는 문제이다.

 

처음에는 주인공이 이동하면서 적을 처치하는 방식으로 구현하였는데,

이 과정에서 문제가 많이 발생하여 생각을 전환해서

적을 모두 처치할 수 있는 조건(정확히는 처치할 수 없는 조건)을 찾아서 해결하였다.

주인공이 적을 처치하는 조건은 이동하면서 좌우에 있는 적을 처치하는 것으로

대각선으로 이동할 수 있으므로 주인공의 위치에서 상하좌우에 있는 적은 처치하지만,

대각선에 있는 적은 처치할 수 없다는 것이다.

 

따라서 주인공의 이동을 구현하고, 각 이동을 따라가면서 적을 발견하면

이 적은 처치할 수 없는 적이므로 모두 처치할 수 없다고 판단하고

"Kiriya"를 출력하도록 구현하였다.

만약 적을 발견하지 못하면 "Lena"를 출력하도록 하였다.

 

문제를 따라가면 주인공이 갈 수 있는 지점들을 모두 확인하면서

경로에 있는 적을 처치하는 방식으로 구현하는 것이 바람직하나,

문제의 의도를 파악하고 생각을 전환해서 처치할 수 없는 경우를 찾아서 해결한 문제였다.