글 읽기 - 말이 되고픈 원숭이 방문여부 배열을 2차원으로 사용하면 안되나요?

rpfdjq3 3년 전 0

안녕하세요

혼자서 생각하다 풀이에 실패를 해서 다른분들의 풀이를 보니

방문 여부에 관한 배열을 3차원으로 작성해 몇번의 horse moving을 통해 해당지점에 갔는지를 기록하여 문제를 푸는것이 일반적이더라구요.

저는 방문 여부 배열을 2차원으로 작성해 horse moving의 값( K - n_moving) 을 기록하는 방식으로 했습니다.

그리고 한칸씩 움직일 때 이미 horse moving 으로 들렸던 곳이라면 현재 horse moving의 값과 비교해 현재가 더 큰 (horse moving을 할 수 있는 횟수) 값을 가지고 있다면 재방문하는 지점을 queue에 넣습니다.

위와 같은 방법을 사용하면 BFS 알고리즘 특성상 horse moving을 우선적으로 사용하다 목적지에 도달하지 못하는 경우를 다시 재갱신 할 수 있다고 생각이 되어 풀이가 될거라 생각을 했는데 6%에서 바로 틀렸네요. 제 아이디어가 어떻게 틀렸는지 알려주시면 감사하겠습니다.

코드에 오류가 있을수도있습니다. 저는 못찾겠네요 ㅜ

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int K, W, H;


queue< pair<int, int> > q;

int move_x[] = {-1, 1, 0, 0};
int move_y[] = {0, 0, -1, 1};

int move_x_horse[] = {-2, -2, 2, 2, 1, -1, 1, -1};
int move_y_horse[] = {-1, 1, -1, 1, -2, -2, 2, 2};

int map[201][201];
int dist[201][201];
int using_K[201][201];

int BFS() {
	q.push(make_pair(1, 1));
	int shortest = 50000;

	while(!q.empty()) {
		int cur_x = q.front().first;
		int cur_y = q.front().second;

		q.pop();

		int next_x, next_y;
		for(int i = 0; i < 4; i++) {
			next_x = move_x[i] + cur_x;
			next_y = move_y[i] + cur_y;
			if (next_x >= 1 && next_x <= H && next_y >= 1 && next_y <= W &&
				map[next_x][next_y] == 0) {
				// 이미 들렸던 곳이 horse moving을 했다면
				if (dist[next_x][next_y] > 0 && using_K[next_x][next_y] < using_K[cur_x][cur_y]) {
					q.push(make_pair(next_x, next_y));
					dist[next_x][next_y] = dist[cur_x][cur_y]+1;
					using_K[next_x][next_y] = using_K[cur_x][cur_y];
					if (next_x == H && next_y == W) {
						return dist[next_x][next_y];
					}
				}
				else if(dist[next_x][next_y] == 0) {
					q.push(make_pair(next_x, next_y));
					dist[next_x][next_y] = dist[cur_x][cur_y]+1;
					using_K[next_x][next_y] = using_K[cur_x][cur_y];
					if (next_x == H && next_y == W) {
						return dist[next_x][next_y];
					}
				}
			}
		}
		if (using_K[cur_x][cur_y] > 0) {
			for(int i = 0; i < 8; i++) {
				next_x = move_x_horse[i] + cur_x;
				next_y = move_y_horse[i] + cur_y;
				if (next_x >= 1 && next_x <= H && next_y >= 1 && next_y <= W &&
					map[next_x][next_y] == 0 && dist[next_x][next_y] == 0) {

					q.push(make_pair(next_x, next_y));
					dist[next_x][next_y] = dist[cur_x][cur_y]+1;
					using_K[next_x][next_y] = using_K[cur_x][cur_y] - 1;
					if (next_x == H && next_y == W) {
						return dist[next_x][next_y];
					}

				}
			}
		}
		
	}
	return -1;
}

int main() {
	scanf("%d", &K);
	scanf("%d %d", &W, &H);

	for(int i = 1; i <= H; i++) {
		for(int j = 1; j <= W; j++) {
			scanf("%d", &map[i][j]);
            using_K[i][j] = K;
		}
	}

	int result = BFS();
	printf("%d\n", result);
	

	return 0;
}

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