<Baekjoon> #1442 BFS_벽 부수고 이동하기 2 c++

Google 아니고 Joogle·2022년 2월 13일
0

Baekjoon

목록 보기
33/47
post-thumbnail

Velog Posting #2206 벽 부수고 이동하기
#1442 벽부수고 이동하기 2

벽 부수고 이동하기 첫 번째 문제와 다른 점은 첫 번째는 최대 1개까지 벽을 부술 수 있었지만 이번엔 K개까지 부술 수 있었다. 그래서

bool discovered[MAX][MAX][2]에서
bool discovered[MAX][MAX][10] 로 바꾸고 (K의 Max가 10이기 때문에)
다음 위치가 벽이고 현재까지 부순 벽의 수가 K개 미만 일 때 벽을 한 개 부수고 다음 지점을 방문한다

if (map[nx_y][nx_x] == PATH && !discovered[nx_y][nx_x][brk]) {
	discovered[nx_y][nx_x][brk] = true;
	q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk, cnt+1)));
}
else if (map[nx_y][nx_x] == WALL && brk < K) {
	discovered[nx_y][nx_x][brk+1] = true;
	q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk+1, cnt + 1)));
}

그런데 이렇게 하니 계속 시간 초과가 떠서 다른 사람의 코드를 참조했다

if (!discovered[nx_y][nx_x][brk]) {
	if (map[nx_y][nx_x] == PATH) {
		discovered[nx_y][nx_x][brk] = true;
		q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk, cnt + 1)));
	}
	else if (map[nx_y][nx_x] == WALL && brk < K) {
		discovered[nx_y][nx_x][brk + 1] = true;
		q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk + 1, cnt + 1)));
	}
}

먼저 다음 위치가 한 번도 방문 되지 않았을 때를 전제로 하고 약간 수정한 건데 어디서 그렇게 시간 차이가 나는 건지 모르겠다 ㅠㅠ cin, cout 에서 시간 초과가 난건지도..

전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;
const int MAX = 1001;
const int PATH = 0;
const int WALL = 1;
int N, M,K;

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

bool discovered[MAX][MAX][10];
vector<vector<int>> map;

void input() {
	memset(discovered, false, sizeof(discovered));
	cin >> N >> M >> K;
	map = vector<vector<int>>(N, vector<int > (M));
	for (int i = 0; i < N; i++) {
		string tmp;
		cin >> tmp;
		for (int j = 0; j < M; j++) {
			int num = tmp[j] - '0';
			map[i][j]=num;
		}
	}
}
int dfs() {
	queue <pair<pair<int, int>, pair<int, int>>> q;
	q.push(make_pair(make_pair(0, 0), make_pair(0, 1)));
	discovered[0][0][0] = true;

	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int brk = q.front().second.first;
		int cnt = q.front().second.second;
		q.pop();

		if (y == N - 1 && x == M - 1) return cnt;

		for (int i = 0; i < 4; i++) {
			int nx_y = y + dy[i];
			int nx_x = x + dx[i];

			if (nx_y < 0 || nx_x < 0 || nx_y >= N || nx_x >= M) continue;
			
			if (!discovered[nx_y][nx_x][brk]) {
				if (map[nx_y][nx_x] == PATH) {
					discovered[nx_y][nx_x][brk] = true;
					q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk, cnt + 1)));
				}
				else if (map[nx_y][nx_x] == WALL && brk < K) {
					discovered[nx_y][nx_x][brk + 1] = true;
					q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk + 1, cnt + 1)));
				}
			}
			//if (map[nx_y][nx_x] == PATH && !discovered[nx_y][nx_x][brk]) {
			//	discovered[nx_y][nx_x][brk] = true;
			//	q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk, cnt+1)));
			//}
			//else if (map[nx_y][nx_x] == WALL && brk < K) {
			//	discovered[nx_y][nx_x][brk+1] = true;
			//	q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk+1, cnt + 1)));
			//}
		}
	}
	return -1;
}
int main() {
	input();
	printf("%d\n", dfs());
	return 0;
}

profile
Backend 개발자 지망생

0개의 댓글