[백준] 2206번: 벽 부수고 이동하기 [C#]

 

문제의 조건 자체는 엄청 쉬워보였다.

일반적인 bfs문제에 그저 블록 파괴 기능만 추가하면 의외로 쉽게 풀릴 줄 알았다... 그 때는...

접근 1)  더이상 순회 불가능 시 벽 파괴해보기

우선 그래프를 순회하며 만난 벽들을 모두 리스트에 담아 기록해둔다.

이후 큐의 모든 원소를 소모하였을 때, 도착점에 도달하지 못했다면, 리스트에서 벽을 하나씩 꺼내어 해당 벽을 부수고, 다시 순회를 해 주었다.

문제 1)  너무 비효율적인 순회

접근법 자체는 빠르게 떠올렸지만, 그리 좋은 접근법은 아니었다. 입력대로 초기화 될때의 상태를 간직하는 원본 그래프를 준비하고, 순회 시 마다 복사본 그래프를 만들어 순회를 해주었는데, 이건 메모리 측면에서나, 실행시간 측면에서나 너무 비효율적이었다.

문제 2)  한번에 순회를 완료했을때 문제.

이게 가장 큰 문제였다. 예제들은 모두 한번에 순회가 불가능했기  때문에 벽을 한번 부수고 순회하는 것이 최단거리였다.

하지만  https://www.acmicpc.net/board/view/147795  이 예제대로 막힌 벽 없이 한번에 순회가 완료되면 바로 메소드가 종료되어 올바른 답을 얻을 수 없었다.

때문에 다른 접근법을 찾아보기로 했다.

보완 1)  사용하는 그래프를 2개로 제한해보기

기존에 순회할 때 마다 무한정 늘어나는 그래프의 수를 제한하고자, 벽을 부수지 않는 경우, 벽을 부수는 경우 둘로 나누어 두 그래프만 사용해보기로 했다.

두 그래프를 유기적으로 묶어, 일반 그래프가 벽을 만나면, 벽을 부수는 그래프의 값을 증가시키고, 다시 벽을 부수는 그래프가 일반 그래프에 영향을 주어 순회를 하는 방식으로 해보았다.

또한 계속해서 벽을 뚫는것을 방지하기 위해, 벽이 벽을 만나면 순회하지않고, 건너뛰기로 했다.

해당 알고리즘을 그힘으로 표현

문제 3)  벽을 한번 이상 부셔버림

알고리즘 특성상 연속된 벽은 통과 못하지만, 띄엄띄엄 존재하는 벽이라면 무한정으로 뚫고 지나가버리는 치명적인 문제점이 있었다. 따라서 벽을 몇번 뚫었는지 저장해두어야 한다는걸 깨닳았다.

문제 4) 벽을 부순건지 아닌지의 모호함

첫번째 칸이 0으로 되어있기 때문에, 첫번째 칸이 벽을 만나 벽을 부수게 되었을 때, 값이 1로 되어 벽을 부순 것인지, 벽을 부수지 않은 것인지 판별을 할 수 없는 문제가 있었다.

보완 2)  그래프를 하나로, 방문처리를 set이 아닌 배열로

그래프의 값을 변조하는 방식이 그다지 효과적이지 않다는 것을 깨달았다. 대신에, 기존에 방문처리를 해주던 HashSet 대신 bool 배열을 이용하여 해당 칸을 방문처리를 대신해 주었다. 이럼으로써 4번 문제가 깔끔히 해결되었다.

보완 3) 모든 정보를 저장해두자

지난번에 풀었던 사다리 게임 문제에서 클래스를 만들어 좌표값 , 이동한 거리, 이동할 좌표값을 저장해두었던 것에서 아이디어를 얻었다. 이번엔 튜플을 이용하여 좌표값, 벽을 부신 횟수, 이동한 거리를 저장하기로 하였다.

이 정보들을 바탕으로, 이동가능 여부, 벽 파괴 가능 여부를 판단할 수 있게 되었다.

코드)

using System;
using System.Collections.Generic;
using System.Text;
 
namespace real연습
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader reader = new StreamReader(Console.OpenStandardInput());
            int[] arr = Array.ConvertAll(reader.ReadLine().Trim().Split(), int.Parse);
            Graph g = new Graph(arr[0], arr[1]);
            for (int i = 0; i < arr[0]; i++)
            {
                string str = reader.ReadLine();
                foreach (var a in str)
                {
                    g.graph[i].Add(a - '0');
                }
            }
            Console.WriteLine(g.bfs());
        }
    }
    class Graph
    {
        int width;
        int height;
        public List<List<int>> graph;
        public Graph(int h, int w)
        {
            this.height = h;
            this.width = w;
            graph = new List<List<int>>();
            for (int i = 0; i < height; i++)
            {
                graph.Add(new List<int>());
            }
        }
        public int bfs()
        {
            int[] deltaY = { 1, 0, -1, 0 };
            int[] deltaX = { 0, 1, 0, -1 };
 
            bool[,,] visited = new bool[height, width,2];
            Queue<Tuple<int, int, int, int>> qu = new Queue<Tuple<int, int, int, int>>();
            qu.Enqueue(new Tuple<int, int, int, int>(0, 0, 0, 1));
            // y, x, 벽 부순 횟수, 거리
            visited[0, 0, 0] = true;
            while(qu.Count!= 0)
            {
                Tuple<int, int, int, int> current = qu.Dequeue();
                if (current.Item1 == height - 1 && current.Item2 == width - 1)
                {
                    return current.Item4;
                }
                for (int i = 0; i < deltaX.Length; i++)
                {
                    int movedY = current.Item1 + deltaY[i];
                    int movedX = current.Item2 + deltaX[i];
                    if (movedY < 0 || movedY >= height || movedX < 0 || movedX >= width)
                    {
                        continue;
                    }
                    if (visited[movedY, movedX, current.Item3] == true)
                    {
                        continue;
                    }
                    if (graph[movedY][movedX] == 0)
                    {
                        qu.Enqueue(new Tuple<int, int, int, int>(movedY, movedX, current.Item3, current.Item4 + 1));
                        visited[movedY, movedX, current.Item3] = true;
                    }
                    else if (current.Item3 == 0 && graph[movedY][movedX] == 1)
                    {
                        qu.Enqueue(new Tuple<int, int, int, int>(movedY, movedX, current.Item3 + 1, current.Item4 + 1));
                        visited[movedY, movedX, current.Item3 + 1] = true;
 
                    }
                }
            }
 
            return -1;
        }
 
    }
}