글 읽기 - 벽 부수고 이동하기와 같은 방법으로 해결하였는데 시간초과가 발생합니다

disdong123 3년 전 0

새로 입력받는 k에 대한 내용을 제외하고는 같은 코드인데 시간초과가 발생합니다

다른 분들의 통과된 코드를 보아도 논리적으로는 같은 일을 하는 것 같은데, 어떤 부분이 잘못된건가요?

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <climits>
#include <map>
using namespace std;

int n, m, k, a[1001][1001];
bool check[1001][1001][11];
int dx[] = { 0,1,0,-1 };
int dy[] = { -1,0,1,0 };
struct Node {
	int x, y, cnt, broken;
	Node(int x, int y, int cnt, int broken)
		:x(x), y(y), cnt(cnt), broken(broken) {}
};
int bfs(int x, int y) {
	check[x][y][1] = true;
	queue<Node> q;
	q.push(Node(x, y, 1, 0));
	while (!q.empty()) {
		x = q.front().x;
		y = q.front().y;
		int cnt = q.front().cnt;
		int broken = q.front().broken;
		if (x == n && y == m) return cnt;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = dx[i] + x;
			int ny = dy[i] + y;
			if (nx > n || ny > m || nx <= 0 || ny <= 0 || check[nx][ny][broken]) continue;
			if (a[nx][ny] && broken >= k) continue;
			if (a[nx][ny] && broken < k) {
				check[nx][ny][broken + 1] = true;
				q.push(Node(nx, ny, cnt + 1, broken + 1));
				continue;
			}
			check[nx][ny][broken] = true;
			q.push(Node(nx, ny, cnt + 1, broken));
		}
	}
	return -1;
}

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

	string str[1001];
	for (int i = 1; i <= n; i++)
		cin >> str[i];

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < m; j++) {
			a[i][j+1] = str[i][j] - '0';
		}
	}
	
	cout << bfs(1, 1) << endl;
}

gumdung 3년 전 1

42,43 번째줄 보시면 만약 벽이 없으면 그냥 바로 큐에 넣고 계시는데 저렇게 하시면 이미 지나왔던 벽이 아니었던 길도 지나왔는지 아닌지를 확인할 수 없기 때문에 다시 되돌아가버립니다. 그러면 이미 상하좌우를 확인한 자리를 또다시 확인하게 되니 큐에는 무한정으로 들어가게 되겠죠.

check 배열을 통해 이미 지나온 길인지를 먼저 확인하시고 큐에 넣어보세요.

disdong123 3년 전 0

그부분은 35번째줄의 check[nx][ny][broken]에서 확인하는것으로 생각되는데 아닌가요??

아니면 다른 부분을 말씀하시는건가요?

gumdung 3년 전 1

저가 직접 코드를 돌려보진 못해서 맞는지는 모르겠지만 현재 작성자님의 코드를 보면 broken+1을 큐에 넣으시고 확인은 broken으로 하시는데 만약 현재까지 벽을 2번 부셨고 벽을 한번 더 부셔야 될 상황이라면 2+1 = 3 의 broken을 큐에 넣게 되겠죠.

그리고 이 broken = 3 의 큐를 뽑아냈을때 그 전의 위치를 다시 돌아갈 필요가 없음에도 불구하고 방문 확인은 broken=3으로 확인해버리니 다시 큐에 넣게 되지 않을까요?

막상 방문확인은 broken=2로 하셨을텐데요?

제가 말한게 조금의 도움이 되는 멘트였으면 좋겠네요.

disdong123 3년 전 0

아 그렇네요.. check[][][broken+1] 을 체크하지 않아서 시간초과가 된 것 같습니다. 답변 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

벽 부수고 이동하기와 같은 방법으로 해결하였는데 시간초과가 발생합니다

disdong123 3년 전 0

gumdung 3년 전 1

disdong123 3년 전 0

gumdung 3년 전 1

disdong123 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말