말이 되고픈 원숭이

 

좀 전형적이지 않은 BFS문제

사실 처음에 DFS로 풀었는데, 시간초과가 날거같아서 방향을 회선했다.(DFS로 할경우 코드 수는 매우 줄지만, 해당문제의 시간제한 + 예상 가짓수를 보면 절대로 DFS를 해선안된다)

 

먼저 DFS코드를보자

#include<iostream>
#include<cstdio>
#include<utility>

using namespace std;

int k, r, c;
int map[200][200];
bool d[200][200];
int ck[200][200];
pair<int, int> sp;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int hx[] = { -2,-1,-2,-1,1,2,2,1 };
int hy[] = { -1,-2,1,2,-2,-1,1,2 };
int ans = 100000;

void dfs(int x, int y, int kk, int cnt) {
	if (cnt > ans) return;
	if (x == r - 1 && y == c - 1) {
		if (cnt < ans) ans = cnt;
		return;
	}
	
	if (kk < k) {
		for (int i = 0; i < 8; i++) {
			int nx = x + hx[i]; int ny = y + hy[i];
			if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
				if (map[nx][ny] != 1 && d[nx][ny] == false) {
					d[nx][ny] = true;
					dfs(nx, ny, kk + 1, cnt + 1);
					d[nx][ny] = false;
				}
			}
		}
	}
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i]; int ny = y + dy[i];
		if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
			if (map[nx][ny] != 1 && d[nx][ny] == false) {
				d[nx][ny] = true;
				dfs(nx, ny, kk + 1, cnt + 1);
				d[nx][ny] = false;
			}
		}
	}
}

int main() {
	cin >> k >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> map[i][j];
		}
	}
	sp.first = 0; sp.second = 0;
	dfs(0, 0,0,0);
	if (ans == 100000)
		cout << -1 << endl;
	else cout << ans << endl;
}

 

위와 같이 굉장히 간결하게 풀수있다. 특히나 2차원 배열만써서 푸는건 아마 여태까지 해왔던 것중에 제일 쉬운게 아닐까 싶다.  하지만, 말이되는경우의 수가 많아지고, 할경우, 재귀 스택이 엄청쌓일걸 생각하면 절대로 좋은풀이가 아니다.

 

#include<iostream>
#include<cstdio>
#include<queue>
#include<utility>

using namespace std;

struct monkey {
	int x = 0, y = 0;
	int k = 0; int d = 0;
	monkey(int x, int y, int k, int d) {
		this->x = x;
		this->y = y;
		this->k = k;
		this->d = d;
	}
};
int k, r, c;
int map[201][201];
bool d[201][201][31];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int hx[] = { -2,-1,-2,-1,1,2,2,1 };
int hy[] = { -1,-2,1,2,-2,-1,1,2 };
int ans = 100000000;

bool check(int nx, int ny) {
	if (nx >= 0 && nx < c && ny >= 0 && ny < r) {
		return true;
	}
	return false;
}

int bfs(monkey m) {
	queue<monkey> q;
	q.push(m);
	d[m.x][m.y][m.k] = true;
	while (!q.empty()) {
		monkey mon = q.front();
		q.pop();
		int x = mon.x; int y = mon.y; int cnt = mon.k; int an = mon.d;
		if (x == c - 1 && y == r - 1) {
			return an;
		}
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i]; int ny = y + dy[i];
			if (check(nx, ny)) {
				if (map[nx][ny] != 1 && d[nx][ny][cnt] == false) {
					d[nx][ny][cnt] = true;
					
					q.push(monkey(nx, ny, cnt, an + 1));
				}
			}
		}
		if (cnt < k) {
			for (int i = 0; i < 8; i++) {
				int nx = x + hx[i]; int ny = y + hy[i];
				if (check(nx, ny)) {
					if (map[nx][ny] != 1 && d[nx][ny][cnt + 1] == false) {
						d[nx][ny][cnt + 1] = true;
						q.push(monkey(nx, ny, cnt + 1, an + 1));
					}
				}
			}
		}
	}
	return -1;
}

int main() {
	cin >> k >> r >> c;
	for (int i = 0; i < c; i++) {
		for (int j = 0; j < r; j++) {
			cin >> map[i][j];
		}
	}
	monkey m(0,0,0,0);
	ans = bfs(m);
	if (ans == -1)
		cout << -1 << '\n';
	else cout << ans << '\n';
	
	return 0;
}

BFS 방식의 풀이다.

먼저 BFS로 하면서 제일 많이 고민했던건, 말이 되어서 가는경우를 어떻게 처리해줘야할지였는데,

그냥 다른 함수를쓰거나하는게 너무 귀찮고 오래걸릴것같아서, 방문 배열 D의 차원을 하나 더추가해서 K의 갯수를

세주었다. 그리고나서 BFS하는동안에 끝 포인트에 다다르면 값을 리턴하는 형식으로 바꿔주었고,

문제를 해결할수있었다.