[BOJ]백준 1600번: 말이 되고픈 원숭이/BFS

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

말이 되고픈 원숭이의 소원을 들어주는 문제

이제 백준에서 런타임에러의 원인을 알려주는데 자꾸 DoubleFree 에러가 떠서 내 코드엔 동적할당이 없는데 왜 뜨지??싶었던 문제

하지만!!!!!!!!!!!!문제는!!!!!!!!!!! 함수에서 반환을 제대로 안 해줬던 것이엇다

 

모든 케이스에서 함수 값을 반환하지 않을 때 위와 같은 런타임에러가 발생할 수 있으니 나와 같은 문제를 겪었던 사람은 참고하길 ...

 

해당 문제는 BFS지만 특이하게 원숭이가 말의 이동으로 몇 번 움직였는지 체크해줘야 했다

 

왜냐면 BFS가 다음 좌표의 방문 여부를 체크할 때에는, 값을 갱신하는 행위가 아니라 '체크하는 행위'만 일어나야 했기 때문에

말로 이동한 횟수가 다르다면, 진짜 최소인 case에서 방문 체크가 되어있어서 pass해버릴 수 있기 때문이다

 

그렇기 때문에 visit배열을 3차원으로 구현했다

 

BFS에 특정 이동 조건이 추가되는 경우는 유의해서 구현하자

 

#include <cstdio>
#include <queue>
using namespace std;
int k, w, h, ans, dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, hx[] = { 1,2,2,1,-1,-2,-2,-1 }, hy[] = { -2,-1,1,2,2,1,-1,2 };
int map[205][205], visit[31][205][205];
typedef struct {
	int x, y;
}point;
typedef struct {
	point p;
	int cnt;
}monkey;
queue<monkey> q;
bool safe(int x, int y) { return x >= 0 && x < w && y >= 0 && y < h; }
int bfs() {
	visit[0][0][0] = 1;
	q.push({ {0,0},0 });

	while (!q.empty()) {
		point cur = q.front().p;
		int cnt = q.front().cnt;
		q.pop();

		if (cur.x == w - 1 && cur.y == h - 1) {
			return visit[cnt][cur.y][cur.x] - 1;
		}


		if (cnt<k)
			for (int i = 0; i < 8; i++) {
				int nx = cur.x + hx[i], ny = cur.y + hy[i];
				if (!safe(nx, ny) || visit[cnt+1][ny][nx] || map[ny][nx])continue;
				visit[cnt+1][ny][nx] = visit[cnt][cur.y][cur.x] + 1;
				q.push({ {nx,ny}, cnt+1 });
			}
		for (int i = 0; i < 4; i++) {
			int nx = cur.x + dx[i], ny = cur.y + dy[i];
			if (!safe(nx, ny) || visit[cnt][ny][nx] || map[ny][nx])continue;
			visit[cnt][ny][nx] = visit[cnt][cur.y][cur.x] + 1;
			q.push({ {nx,ny}, cnt });
		}
	}
    return -1;
}
int main() {
	scanf("%d%d%d", &k, &w, &h);
	for (int i = 0; i < h; i++)for (int j = 0; j < w; j++)scanf("%d", &map[i][j]);
	printf("%d", bfs());
	return 0;
}