문제 : https://www.acmicpc.net/problem/2206

서론

크게 어렵게 생각 안했는데 시간초과를 연타로 맞았다.

DFS로 구현했다가 시간초과

같은 아이디어를 BFS로 구현했다가 시간초과

방문배열을 3차원으로 만들었는데 시간초과

큐에서 꺼낸 후 방문체크에서 꺼내기 전 방문체크로 수정해서 통과

많은걸 얻어가는 문제다.

풀이과정

기존의 이동할 곳이 0이면 방문하고 1이면 방문하지 않는것에서

조건을 하나 추가해준다.

1이더라도 내가 지금까지 벽을 뚫은적이 없다면 벽을 뚫은 후 다시는 벽을 뚫지 않겠다고 공표하고 방문한다.

따라서 방문할때마다 내가 기존에 벽을 뚫었는지 안뚫었는지 확인을 해야하므로 확인할 수 있는 변수를 큐에 좌표와 함께 넣어준다.

여기까지가 내 아이디어였는데 그 후 수많은 시간초과를 맛보았다.

그리고 그 해결책의 힌트들은

https://www.acmicpc.net/board/view/27386

여기서 얻을 수 있었다.

구현

//c++

#pragma warning (disable:4996)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>

int map[1001][1001];
int visited[1001][1001][2];
char tmp[1001];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int n, m;

typedef struct st {
	int y;
	int x;
	int breakWall;
}st;

int bfs() {
	std::queue<st>q;
	q.push({ 0,0,0 });
	visited[0][0][0] = 1;

	int cnt = 0;

	while (!q.empty()) {
		int qSize = q.size();
		while (qSize--) {
			int y = q.front().y;
			int x = q.front().x;
			int breakWall = q.front().breakWall;
			q.pop();
			//std::cout << y << " " << x << std::endl;
			if (y == n - 1 && x == m - 1) return cnt + 1;

			for (int i = 0; i < 4; i++) {
				int yy = y + dy[i];
				int xx = x + dx[i];
				if (yy >= 0 && xx >= 0 && yy < n && xx < m && visited[yy][xx][breakWall] == 0) {
					if (map[yy][xx] == 0) {
						q.push({ yy, xx, breakWall });
						visited[yy][xx][breakWall] = 1;
					}
					else if (breakWall == 0) {
						q.push({ yy, xx, 1 });
						visited[yy][xx][1] = 1;
					}
				}
			}
		}
		cnt++;
	}
	return -1;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%s", &tmp);
		for (int j = 0; j < m; j++) {
			map[i][j] = tmp[j] - '0';
		}
	}
	printf("%d", bfs());
}