[백준 2665] 미로만들기 C++

문제

백준 2665 미로만들기 C++

2665번: 미로만들기

풀이

두가지 방법으로 풀었다.

 

첫 번째 방법

1. cnt만큼 벽을 뚫을 수 있게 설정해준다.

2. BFS() 함수를 실행하여 최대 cnt만큼 벽을 뚫으면서 도착지점에 도달할 수 있는지 없는지 확인한다.

3-1. 도착할 수 있다면 true를 return 하고 현재 cnt를 출력한다.

3-2. 도착할 수 없다면 cnt를 1증가시키고 다시 BFS() 함수를 실행한다.

 

방문 체크를 3차원 배열로 했는데 (y좌표, x좌표, cnt : 벽 부순 횟수) 쓸데없이 cnt를 크게 잡은 거 같다.

[50][50][2500]으로 잡았더니 메모리가 꽤 크게 잡혔는데, 정작 시간 초과는 안 나서 신기할 따름.

 

두 번째 방법

deque를 활용한다.

1. 시작점 부터 BFS()를 실행한다.

2. 다음 방을 한 번도 방문하지 않았거나(여기서는 minBreakCnt가 -1인 경우) 현재 경로가 더 유망한 경우에 아래 과정을 실행한다. 이미 방문했는데 현재 경로가 더 유망하지 않은 경우에는 실행하지 않는다.

3-1. 다음 방이 흰 방이라면 벽을 부술 필요가 없다. deque에 제일 앞에 Node를 삽입한다.

3-2. 다음 방이 검은 방이라면 벽을 부숴야 한다. dequeue의 제일 뒤에 Node를 삽입한다.

4. minBreakCnt[n - 1][n - 1] 값을 출력한다.

소스 코드

첫 번째 방법

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
 
int N;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int map[50][50];
bool visited[50][50][2500];
 
struct Node
{
    int x = 0;
    int y = 0;
    int cnt = 0;
};
 
bool BFS(int maxCnt)
{
    memset(visited, 0, sizeof(visited));
    queue<Node> q;
    q.push({ 0, 0, 0});
 
    while (!q.empty())
    {
        int cx = q.front().x;
        int cy = q.front().y;
        int cnt = q.front().cnt;
        q.pop();
 
        if (cx == N - 1 && cy == N - 1)
            return true;
 
        for (int i = 0; i < 4; i++)
        {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[ny][nx][cnt])
            {
                visited[ny][nx][cnt] = true;
 
                if (map[ny][nx] == 1)
                {
                    q.push({ nx, ny, cnt });
                }
                else if (cnt < maxCnt)
                {
                    q.push({ nx, ny, cnt + 1 });
                }
            }
        }
    }
 
    return false;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> N;
 
    string input;
 
    for (int i = 0; i < N; i++)
    {
        cin >> input;
 
        for (int j = 0; j < N; j++)
        {
            map[i][j] = input[j] - '0';
        }
    }
 
    int cnt = 0;
 
    while (1)
    {
        if (BFS(cnt))
            break;
 
        cnt += 1;
    }
 
    cout << cnt;
 
    return 0;
}

두 번째 방법

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
 
int N;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int map[50][50];
// 시작 지점에서 해당 지점까지 도달할 때, 벽을 부수는 최소 횟수
int minBreakCnt[50][50];
 
struct Node
{
    int x = 0;
    int y = 0;
    int cnt = 0;
};
 
void BFS()
{
    deque<Node> q;
    q.push_front({ 0, 0, 0 });
 
    while (!q.empty())
    {
        int cx = q.front().x;
        int cy = q.front().y;
        int cnt = q.front().cnt;
        q.pop_front();
        minBreakCnt[0][0] = 0;
 
        for (int i = 0; i < 4; i++)
        {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                int nCnt = minBreakCnt[ny][nx];
 
                // 흰 방
                if (map[ny][nx] == 1)
                {
                    if (nCnt == -1 || cnt < nCnt)
                    {
                        minBreakCnt[ny][nx] = cnt;
                        q.push_front({ nx, ny, cnt });
                    }
                }
                // 검은 방
                else if (nCnt == -1 || cnt + 1 < nCnt)
                {
                    minBreakCnt[ny][nx] = cnt + 1;
                    q.push_back({ nx, ny, cnt + 1 });
                }
            }
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> N;
 
    string input;
 
    for (int i = 0; i < N; i++)
    {
        cin >> input;
 
        for (int j = 0; j < N; j++)
        {
            map[i][j] = input[j] - '0';
            minBreakCnt[i][j] = -1;
        }
    }
 
    BFS();
    cout << minBreakCnt[N - 1][N - 1];
 
    return 0;
}