백준 2665 - 미로만들기 (C++)

 

1행 1열에서 시작해서, n행 n열까지 도달하기 위해선, 몇개의 검은 방을 하얀 방으로 바꾸어야 하는 가를 구하는 문제이다.

 

가는 길이 검은방으로 막혀있다면, 검은 방을 하얀 방으로 바꿔 지나갈 수 있는 길로 만들 수 있다. 이렇게, 방을 바꿔가며 목적지까지 이동할 때, 방의 색을 바꾸는 최소의 수를 구하면 된다.

 

문제 풀이

 

본인은 BFS를 활용하여 해결하였다. 행렬의 최대 크기가 50인만큼, 완전탐색을 하여도 부담이 없기 때문이다.

 

또한, 본인이 푼 방식은 50개의 칸만 탐색하는 완전탐색이 아니라, 이미 거쳤던 곳도 다시 방문하여 탐색하는 방식인데 행렬의 크기가 커질수록 연산 부담이 커지겠지만, 문제에서 주어진 최대 행렬 크기가 50 x 50 이기 때문에 사용할 수 있었다.

 

먼저 2개의 이차원 배열을 준비하였다.

 

하나는 맵 배열이고, 하나는 방을 바꾼 횟수를 저장한 배열이다.

맵 배열을 Map, 방을 바꾼 횟수를 저장한 배열을 ChangeCount라고 하겠다.

 

ChangeCount에서 (i, j)가 의미하는 것은 (1, 1)에서 (i, j)로 갈 때, 검은 방을 하얀 방으로 바꾸는 최소 횟수이다.

 

탐색 방식은 아래와 같다.

 

먼저, 첫 번째 칸 (1, 1)을 큐에 삽입한다.

이후, 큐의 size가 0이 될 때까지 반복문을 돌린다.

 

반복문 내부에선, 큐의 front를 기준으로 4방향을 탐색한다.

 

다음에 나아갈 방향이 검은 방이라면, 현재 칸의 ChangeCount + 1과 다음 칸의 ChangeCount를 비교한다.

만약, 다음 칸의 ChangeCount 값이 현재 칸의 ChangeCount + 1 보다 같거나 작다면, 다음 칸으로 나아가지 않는다.

 (ChangeCount는 최소값을 저장하는 배열이기 때문에, 최소 값을 갱신할 수 없는 상황이라면 나아가지 않는다.)

 

다음에 나아갈 방향이 하얀 방이라면, 현재 칸의 ChangeCount와 다음 칸의 ChangeCount를 비교한다.

만약, 다음 칸의 ChangeCount 값이 현재 칸의 ChangeCount보다 같거나 작다면, 다음 칸으로 나아가지 않는다.

 

다음에 나아갈 방향이 검은 방일 때와 하얀 방일 때 모두 처리하는 과정은 똑같다. 다만, 검은 방인 경우 해당 방의 색을 바꿔주어야 하기 때문에, ChangeCount에 1을 더해서 비교해주고 있다.

 

이 과정을 모두 마치고 나면, ChangeCount의 (n, n)에는 1,1에서 시작해서 n,n에 도착할 때 까지 방의 색을 바꾼 최소 횟수가 저장되어 있을 것이다.

 

풀이 코드

 

int Size = 0;
std::cin >> Size;

std::vector<std::vector<int>> Map(Size, std::vector<int>(Size));
for (int i = 0; i < Size; i++)
{
    std::string Input;
    std::cin >> Input;

    for (int j = 0; j < Size; j++)
    {
        Map[i][j] = Input[j] - '0';
    }
}

 

먼저 입력을 받아주었다.

int로 받으면 한 줄이 하나의 원소에 저장되어 버려서, string으로 받은 뒤 하나씩 분배해주었다.

 

struct Node
{
    int Y = 0;
    int X = 0;
};

 

위치 정보를 저장할 구조체를 선언하였다. std::pair을 사용해도 되지만, 직접 정의한 구조체를 이용해 조금 더 가독성을 높혀보았다.

 

std::vector<std::vector<int>> ChangeCount(Size, std::vector<int>(Size, 10000000));

ChangeCount[0][0] = 1 - Map[0][0];

std::queue<Node> BFS;
BFS.push({ 0, 0});

std::vector<int> DirX = { 0, 1, 0, -1 };
std::vector<int> DirY = { -1, 0, 1, 0 };

 

ChangeCount는 위에서 말한 것과 같이 해당 칸으로 이동하는동안 방을 바꾸는 최소 횟수를 저장한 배열이다.

최소 값을 갱신하는 배열이기 때문에 초기값을 충분히 큰 값으로 잡아주었다.

 

다음은 BFS를 하기 위한 queue를 선언하였고, 4방향을 탐색하기 위한 Dir 배열도 선언해주었다.

while (BFS.size() > 0)
{
    Node CurNode = BFS.front();
    BFS.pop();

    for (int i = 0; i < 4; i++)
    {
        int NextX = CurNode.X + DirX[i];
        int NextY = CurNode.Y + DirY[i];

        if (NextX < 0 || NextY < 0 || NextX >= Size || NextY >= Size)
        {
            continue;
        }

        if (Map[NextY][NextX] == 0)
        {
            if (ChangeCount[CurNode.Y][CurNode.X] + 1 >= ChangeCount[NextY][NextX])
            {
                continue;
            }
            else
            {
                ChangeCount[NextY][NextX] = ChangeCount[CurNode.Y][CurNode.X] + 1;
                BFS.push({ NextY, NextX });
            }
        }
        else
        {
            if (ChangeCount[CurNode.Y][CurNode.X] >= ChangeCount[NextY][NextX])
            {
                continue;
            }
            else
            {
                ChangeCount[NextY][NextX] = ChangeCount[CurNode.Y][CurNode.X];
                BFS.push({ NextY, NextX });
            }
        }
    }
}

 

큐의 최상위 원소를 뽑아서, 4방향을 탐색해주었다.

 

위에서 설명한 것과 같이, 다음에 나아갈 곳이 검은 방이라면 ChangeCount + 1 을 기준으로 대소비교를 하고있으며 하얀 방이라면 ChangeCount를 기준으로 대소비교를 하고 있다.

 

최소값을 갱신할 수 있다면, 해당 방향으로 나아가 계속 최소값을 갱신해주었다.

std::cout << ChangeCount[Size - 1][Size - 1];

return 0;

 

BFS가 끝난 뒤 목적지의 값을 출력해주면 끝이다.

 

코드 전문

#include <iostream>
#include <vector>
#include <queue>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

struct Node
{
    int Y = 0;
    int X = 0;
};

int main()
{
    Init();

    int Size = 0;
    std::cin >> Size;

    std::vector<std::vector<int>> Map(Size, std::vector<int>(Size));
    for (int i = 0; i < Size; i++)
    {
        std::string Input;
        std::cin >> Input;

        for (int j = 0; j < Size; j++)
        {
            Map[i][j] = Input[j] - '0';
        }
    }

    std::vector<std::vector<int>> ChangeCount(Size, std::vector<int>(Size, 10000000));

    ChangeCount[0][0] = 1 - Map[0][0];

    std::queue<Node> BFS;
    BFS.push({ 0, 0});

    std::vector<int> DirX = { 0, 1, 0, -1 };
    std::vector<int> DirY = { -1, 0, 1, 0 };

    while (BFS.size() > 0)
    {
        Node CurNode = BFS.front();
        BFS.pop();

        for (int i = 0; i < 4; i++)
        {
            int NextX = CurNode.X + DirX[i];
            int NextY = CurNode.Y + DirY[i];

            if (NextX < 0 || NextY < 0 || NextX >= Size || NextY >= Size)
            {
                continue;
            }
            
            if (Map[NextY][NextX] == 0)
            {
                if (ChangeCount[CurNode.Y][CurNode.X] + 1 >= ChangeCount[NextY][NextX])
                {
                	continue;
                }
                else
                {
                	ChangeCount[NextY][NextX] = ChangeCount[CurNode.Y][CurNode.X] + 1;
                	BFS.push({ NextY, NextX });
                }
            }
            else
            {
                if (ChangeCount[CurNode.Y][CurNode.X] >= ChangeCount[NextY][NextX])
                {
                    continue;
                }
                else
                {
                    ChangeCount[NextY][NextX] = ChangeCount[CurNode.Y][CurNode.X];
                    BFS.push({ NextY, NextX });
                }
            }
        }
    }

    std::cout << ChangeCount[Size - 1][Size - 1];

    return 0;
}