백준 1600번 말이 되고픈 원숭이

https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

 

 

 

 

 

 

 

<접근방법>

bfs 문제 입니다.

전형적인 문제와 조금 다른 점이 있습니다.

 

원숭이가 같은 (y, x) 라는 좌표에 있더라도 능력이 몇 번 남았느냐에 따라 남은 결과가 달라진다는 것 입니다.

(y, x)에서 능력이 1번 남았을 때와 0번 남았을 때를 비교해보면 바로 알 수 있지요.

 

그래서 단순히 좌표만으로 중복체크를 한다면 안된다는 것 입니다.

그럼 중복체크를 어떻게 할까요?

 

같은 좌표와 같은 능력 횟수를 가지고 있다면 결과도 같겠죠?

그러므로 좌표에다가 능력까지 포함한 중복체크를 해줘야합니다.

이것은 중복체크배열을 3차원으로 하면 됩니다.

 

---

 

 

 

<코드>

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

struct point {
	int y, x, cnt, time;
};

int k, n, m, map[200][200];
int dy[12] = { 1, -1, 0, 0,-2, -1, 1, 2, 2, 1, -1, -2 };
int dx[12] = { 0, 0, 1, -1, 1, 2 ,2, 1, -1, -2, -2, -1 };
bool visit[200][200][30] = { false, };


int bfs() {
	queue<point> q;

	q.push({0, 0, k, 0});
	visit[0][0][k] = true;

	while (!q.empty()) {
		point t = q.front();
		q.pop();

		if (t.y == n - 1 && t.x == m - 1) return t.time;

		for (int i = 0; i < 12; i++) {
			int ty, tx, tcnt = t.cnt, ttime = t.time + 1;

			if (i >= 4) {
				if (t.cnt == 0) break;
				tcnt -= 1;
			}
			ty = t.y + dy[i];
			tx = t.x + dx[i];


			if (ty < 0 || ty >= n || tx < 0 || tx >= m) continue;
			if (visit[ty][tx][tcnt] || map[ty][tx] == 1) continue;

			q.push({ty, tx, tcnt, ttime});
			visit[ty][tx][tcnt] = true;
		}
	}
	return -1;
}

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

	cin >> k;
	cin >> m >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}

	cout << bfs() << '\n';
	return 0;
}

 

 

 

---

 

 

 

<느낀 점>

-스택, 메모리, 힙 영역