백준/2206번/벽 부수고 이동하기/골드3

Problem Link: https://www.acmicpc.net/problem/2206

문제 설명

Site: Baekjoon
Number: 2206
Category: BFS
Rank: Gold 3

좌표 0,0에서 시작하여 주어진 N, M의 위치까지 갈 때 최단거리를 구하는 문제이지만, 가는 길에 벽을 한 번은 부실 수 있는 경우를 추가한 문제이다.

처음엔 모든 벽을 하나씩 지우면서 BFS를 돌렸지만, 범위가 1000 * 1000으로 총 100만칸이 넘어가기 때문에 시간 초과가 발생하였다.

시간 초과를 해결하기 위해 BFS를 다음과 같은 상황을 고려하며 진행한다.

• BFS를 진행하며 지점을 Queue에 넣을 때 지나간 칸의 갯수와 벽을 뚫은 적이 있는지를 저장한다.
• 기존에 방문 여부만을 파악하던 bool visited배열이 아닌 int visited배열로 하여 벽을 부수고 간 경우 1, 벽을 부수지 않고 지나간 경우 -1로 정한다.
• 다음 지점을 방문할 때 다음을 확인한다:
  1. 벽이라면 벽을 뚫을 수 있으면 뚫고 방문하고, 없다면 방문하지 않는다.
  2. 벽을 뚫었지만 이미 방문한 지점이라면 방문하지 않는다.
  3. 벽을 뚫지 않았지만 이미 방문한 지점이라면 방문하지 않는다.
  4. N,M 지점이라면 지나간 칸의 갯수를 반환한다.

마지막으로 answer가 9999999라면 -1을 출력, 아니라면 answer을 출력한다.

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

using namespace std;

using TIIIB = tuple<int, int, int, bool>;

int answer = 9999999;
int N, M;

int arr[1001][1001];
int visited[1001][1001];

int dirx[4] = {0, -1, 0, 1};
int diry[4] = {-1, 0, 1, 0};

void BFS()
{
    queue<TIIIB> q;

    q.emplace(0, 0, 1, false);

    while(!q.empty())
    {
        int x = get<0>(q.front());
        int y = get<1>(q.front());
        int cnt = get<2>(q.front());
        int bWall = get<3>(q.front());
        q.pop();

        if (cnt >= answer)
            return;

        if(x == N-1 && y == M-1)
        {
            answer = min(answer, cnt);
            return;
        }

		for(int i = 0; i < 4; i++)
        {
            int newx = x + dirx[i];
            int newy = y + diry[i];
            int newbWall = bWall;

            if (newx < 0 || newx > N - 1 || newy < 0 || newy > M - 1)
                continue;

            if (arr[newx][newy] == 1)
            {
                if (newbWall)
                    continue;
                else
                    newbWall = true;
            }

            if (visited[newx][newy] != 0 && newbWall)
                continue;
            if (visited[newx][newy] == -1 && !newbWall)
                continue;

            if (!newbWall)
                visited[newx][newy] = -1;
            else
                visited[newx][newy] = 1;

            q.emplace(newx, newy, cnt + 1, newbWall);
        }
    }

}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> N >> M;

	for(int i = 0; i < N; i++)
    {
	    for(int j = 0; j < M; j++)
	    {
            char c;
            cin >> c;
	    }
    }

    visited[0][0] = -1;

    BFS();


    if (answer == 9999999)
        cout << -1;
    else
        cout << answer;

    return 0;
}