어렵다...

처음에는 단순하게 모든 벽을 한번씩 부숴본다 생각하고

이중 for문으로 모든 벽들을 한번씩 지우고 BFS()를 돌려주었다.

물론 시간초과가 날거같아서 조건을 걸었는데

벽(1) 동서남북에 하나라도 공간(0)이 있어야 BFS를 돌린다.

모든 테스트 케이스들이 통과하지만 결국 시간초과가 났다.

다른 풀이를 참고하게 되었다..

상당히 참신한 방법을 사용한다.

---

풀이

BFS를 돌기 위해 방문한 위치를 식별하기 위해 visited 배열을 사용한다는것은 기본인데

여기서 벽을 하나 뚫고 온것인지 아니면 벽을 안뚫고 온것인지 구별이 필요하다.

• 벽을 뚫고 왔다면 앞으로 더 뚫을 수는 없고

• 벽을 안뚫고 왔다면 앞으로 하나 뚫을 수 있다는 말이다.

고로 visited 배열에 이 정보를 담아줘야 하는데 그래서 3차원 배열을 사용한다.

int visited [1001][[1001][2];

visited[i][j][0] : 벽을 부수지 않고 왔을 때 체크
visited[i][j][1] : 벽을 부수고 왔을 때 체크

---

코드

#include <bits/stdc++.h>

using namespace std;

int n, m;
int Map[1001][1001];
int visited[1001][1001][2];

int Min = 999999999;

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

typedef struct node
{
	int x;
	int y;
	int cnt;
	int flag;
};

queue<node> q;

int bfs()
{
	visited[0][0][0] = 1;
	q.push(node{ 0,0,1,0 });

	while (!q.empty())
	{
		int cx = q.front().x;
		int cy = q.front().y;
		int cnt = q.front().cnt;
		// flag가 1이면 이미 벽을 한번 부수고 여기까지 왔음을 의미
		int flag = q.front().flag;

		q.pop();

		if (cx == n - 1 && cy == m - 1)
			return cnt;

		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 >= m)
				continue;

			// 다음칸이 벽이고 아직 부순 벽이 없다면
			if (Map[nx][ny] == 1 && flag == 0)
			{
				// 다음 칸은 벽을 부순 visited로 체크 해주고
				visited[nx][ny][1] = 1;
				q.push(node{ nx, ny, cnt + 1, 1 });
			}

			// 다음칸이 빈칸이고 방문 되지 않았다면
			if (Map[nx][ny] == 0 && !visited[nx][ny][flag])
			{
				visited[nx][ny][flag] = 1;
				q.push(node{ nx, ny, cnt + 1, flag });
			}
		}
	}

	return -1;
}

int main()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < m; j++)
		{
			Map[i][j] = str[j] - '0';
		}
	}

	int result = bfs();

	cout << result;

	return 0;
}

---

후기

처음 방법으로 했을 때 14%까지 올라가길래 좋다고 계속 하다가 결국 시간초과의 늪에서 벗어나지 못하고 방법을 찾게되었다.

이런 문제가 나오면 현장에서 생각이 날 수 있을지 걱정이다.