글 읽기 - 제가 접근하는 방식이 틀렸나요??

jokerkwu 5년 전 0

처음에 bfs를 벽개수만큼 돌리다보니 시간초과가 나서 질문검색에 있는 글들을 확인해보니
bfs를 한번만 돌려도 가능하다는 글을 보고
bfs를 한번만 돌려서 벽부수고 이동과 벽안부수고 이동을 나눠서 문제를 접근하였습니다.
테스트케이스와 질문검색에 있는 예외케이스 전부 돌려도 정상적으로 출력이 되는데
바로 틀렸습니다가 나오는데 혹시 또다른 예외케이스를 알 수 있을까요?

#include<iostream>
#include<queue>
#include<vector>
#include<string.h>
using namespace std;
#define MAX 1001
int n, m, ans;
bool visited1[MAX][MAX];		//벽을 안부시고 이동 체크
bool visited2[MAX][MAX];		//벽 부셨을때 이동 체크
int board[MAX][MAX];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
typedef pair<int, pair<int, pair<int, int>>> piii;
void bfs() {
	priority_queue<piii, vector<piii>, greater<piii>>pq;	//이동횟수, 벽부순횟수,x,y
	pq.push(make_pair(0, make_pair(0, make_pair(0, 0))));
	while (!pq.empty()) {
		int wallBreak = pq.top().second.first;
		int moveCnt = pq.top().first;
		int currentX = pq.top().second.second.first;
		int currentY = pq.top().second.second.second;
		pq.pop();
		//도착했을시
		if (currentX == (m - 1) && currentY == (n - 1)) {
			if (ans == 0) {
				ans = moveCnt + 1;
			}
			else if (ans > (moveCnt + 1)) {
				ans = moveCnt + 1;
			}
			return;
		}
		//벽안부수고 현재 좌표에 방문 안했거나 벽부수고 현재좌표에 방문 안했을시
		if ((wallBreak == 0 && !visited1[currentY][currentX]) || (wallBreak == 1 && !visited2[currentY][currentX])) {
			if (wallBreak == 0) {//벽 안부셨다면
				visited1[currentY][currentX] = true;
			}
			else {	//벽 부셨다면
				visited2[currentY][currentX] = true;
			}
			for (int i = 0; i < 4; i++) {
				int nextX = currentX + dx[i];
				int nextY = currentY + dy[i];
				if (nextX >= 0 && nextX < m&&nextY >= 0 && nextY < n) {
					if (wallBreak == 0) {//벽 안부수고 다음 좌표가 빈경우
						if (!visited1[nextY][nextX] && board[nextY][nextX] == 0) {
							pq.push(make_pair(moveCnt + 1, make_pair(wallBreak, make_pair(nextX, nextY))));
						}//벽인경우
						else if (board[nextY][nextX] == 1) {
							pq.push(make_pair(moveCnt + 1, make_pair(1, make_pair(nextX, nextY))));
						}
					}
					else {//벽부수고 다음좌표가 비어있는경우
						if (!visited2[nextY][nextX] && board[nextY][nextX] == 0) {
							pq.push(make_pair(moveCnt + 1, make_pair(1, make_pair(nextX, nextY))));
						}
					}
				}
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	vector<pair<int, int>>v;//x,y
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf_s("%1d", &board[i][j],stdin);
			if (board[i][j] == 1) {
				v.push_back(make_pair(j, i));
			}
		}
	}
	bfs();
	if (ans == 0) {
		cout << "-1" << '\n';
	}
	else {
		cout << ans << '\n';
	}
	return 0;
}


/*

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

ans = 29


5 8
01000000
01010000
01010000
01010011
00010010

ans = 20

5 6
000000
011110
010000
010111
100000

ans = 10

3 3
011
100
110

ans =5

6 9
010001000
010001010
010101010
010101000
010101010
000100010
ans =18

20 20
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000

ans =39


*/