인프런 커뮤니티 질문&답변

 

그대로 따라서 했는데 4번 5번 테스트케이스에서 시간초과가 나왔습니다,,,

3번 확인해도 똑같이 따라 코딩했는데 왜 그런걸까요...?

 

#include <iostream>
#include <queue>
using namespace std;

int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
int board[1001][1001], dis[2][1001][1001];
queue<pair<int, int>> Q;
int w, h;

void BFS(int idx) {//idx = 2부터 시작했니, 3부터 시작했니 판가름할 변수
	while (!Q.empty()) {
		int x = Q.front().first;
		int y = Q.front().second;
		Q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < h&&ny >= 0 && ny < w&&dis[idx][nx][ny]==0) {//경계선
				if (board[nx][ny] != 1) {
					dis[idx][nx][ny] = dis[idx][x][y] + 1;
					Q.push(make_pair(nx, ny));
				}
			}
		}
	}
}

int main() {
	cin.tie(NULL); // 입력빨리하기 위해
	cin >> w >> h;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++)
			cin >> board[i][j];
	}

	int j;
	for (int i = 0; i < h; i++) {
		for (j = 0; j < w; j++) {
			if (board[i][j] == 2) { //영희의 위치찾기
				dis[0][i][j] = 1;//영희로부터의 거리를 1부터 출발
				Q.push(make_pair(i, j));
				BFS(0);
				break;
			}
		}
		if (j < w)break;
	}

	for (int i = 0; i < h; i++) {
		for (j = 0; j < w; j++) {
			if (board[i][j] == 3) {
				dis[1][i][j] = 1;
				Q.push(make_pair(i, j));
				BFS(1);
				break;
			}
		}
		if (j < w)break;
	}

	int min = 2147000000;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (board[i][j] == 4 && dis[0][i][j] > 0 && dis[1][i][j] > 0) {
				int res = dis[0][i][j] + dis[1][i][j];
				if (res < min)min = res;
			}
		}
	}

	cout << min - 2;

	return 0;
}