글 읽기 - [시간초과] 혹시 저와 같은 문제로 안풀리는 분이 있을까하여

dlfrk7 3년 전 19

[시간초과] 혹시 저와 같은 문제로 안풀리는 분이 있을까하여 남깁니다.

56번째 줄에

" visited[ny][nx][w-1] == 0 "

처리를 안해서 시간초과가 났습니다.

생각해보면 당연히

덮어씌우는 숫자가 된다면 최소가 되지 않기때문에

시간초과만의 문제가 아니라, 틀린 답이 나올 수도 있게 만들 것 같습니다.

사실은 제가 많이 부족해서 찾아내고 수정하는데 오래걸렸습니다만,,

혹시라도 비슷한 문제로 고생하실분이 있을까 하여 남깁니다.

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

#define MAX 1001

char map[MAX][MAX];
int visited[MAX][MAX][11] = { 0 };

int N, M, K; // N*M map, K개 까지 부수고 이동 가능

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

struct st {
	int y, x, w;
};

int main() {
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);

	cin >> N >> M >> K;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
		}
	}

	int result = -1;

	queue <st> q;
	q.push({ 1,1,K });
	visited[1][1][K] = 1;

	while (!q.empty()) {

		int y = q.front().y;
		int x = q.front().x;
		int w = q.front().w;

		q.pop();

		if (y == N && x == M) {
			result = visited[y][x][w];
			break;
		}

		for (int i = 0; i < 4; i++) {

			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 1 || ny > N || nx < 1 || nx > M) continue;

			if (map[ny][nx] == '1' && w > 0 && visited[ny][nx][w-1] == 0) {
				visited[ny][nx][w - 1] = visited[y][x][w] + 1;
				q.push({ ny,nx,w - 1 });
			}
			if (map[ny][nx] == '0' && visited[ny][nx][w] == 0) {
				visited[ny][nx][w] = visited[y][x][w] + 1;
				q.push({ ny,nx,w });
			}

		}
	}

	cout << result << "\n";

	return 0;
}

lsyun1234 2년 전 1

와 저도 visited[ny][nx][w-1] == 0 때문에 헤매고 있었는데 이거 바꾸니까 딱 되네요

저같은 경우는 바보같이 visited[ny][nx][w] == 0으로 했네요 ㅋㅋㅋㅋ

감사합니다!

namwon420 7달 전 0

와.. 저도 visited[ny][nx][w-1] == 0 이거 하나 추가하니까 맞았어요.. 감사합니다 ㅠㅠ

hg412 5달 전 0

감사합니다 저도 이거 딱 하나 추가하니까 맞았네요 (__)

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

문제

문제

출처

ICPC

[시간초과] 혹시 저와 같은 문제로 안풀리는 분이 있을까하여

dlfrk7 3년 전 19

lsyun1234 2년 전 1

namwon420 7달 전 0

hg412 5달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말