Baekjoon1600-말이 되고픈 원숭이

백준 사이트 1600 - 말이 되고픈 원숭이 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

BFS문제입니다.
백준에서는 Gold5의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 골드5 치고는 어려운 것 같습니다. 생각할 거리가 생각보다 많기 때문입니다. 구현 자체는 쉬운 편.
• 주의 해야할 점이 입력이 가로의 길이, 세로의 길이로 4와 5를 입력받으면

  4 5
  0 0 0 0 
  0 0 0 0 
  0 0 0 0 
  0 0 0 0 
  0 0 0 0 
  

  이렇게 배열이 생긴다는 것에 주의해야합니다.

• DP로 풀어야겠다고 생각했습니다.
  • 최소 이동 횟수 문제가아닌 모든 경우의 수 문제인줄 알고 DP로 풀려했는데 아닌걸 보고 DP코드를 지웠습니다.
• 일반적인 BFS와 다르게 방문처리릍 특별하게 해줘야합니다.
  • 다음 인풋을 예시로 들면

      1
      5 4 
      0 0 0 0 0
      0 0 0 0 0
      0 0 0 1 1
      0 0 0 1 0
    

    결과는 이렇게 되어야 합니다.

      0 1 0 0 0
      0 2 3 4 0
      0 0 0 x x
      0 0 0 x 5
    

    말처럼 바로 움직여버리면 움직임을 다 소비해버려 다음과 같이 이동할 수가 없습니다.

      0 0 0 0 0
      0 1 2 3 0
      0 0 0 x x
      0 0 0 x -1
    

    그래서 말의 이동횟수에 대한 카운트를 잘 세줘야합니다.
    방문 처리를 미리 해버리면 방문하였기에 접근을 안하고, 방문 처리를 안해버리면 모든 배열을 돌아야하므로 시간초과가 날 것 입니다.

• 해결법은 방문처리 배열의 차원을 하나 더 두는 것입니다.
• 차원을 하나 더 두었기에 말처럼 이동했을 때 방문처리와 원숭이로 이동했을 때 방문처리를 관리할 수 있습니다.

---

5. code

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

const int MAX = 201;
int MAP[MAX][MAX] = { 0, };
bool v[MAX][MAX][32] = { false, };
int W, H, K;

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int horsex[8] = { -1,-2,-2,-1,1,2, 2, 1 };
int horsey[8] = { -2,-1, 1, 2,2,1,-1,-2 };

void Input()
{
	cin >> K;
	cin >> W >> H;
	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j <W; ++j)
			cin >> MAP[i][j];
	}
}

int Solve()
{
	//BFS
	//좌표 값, k 카운트 값, 이동횟수
	memset(v, false, sizeof(v));
	queue < pair<pair<int, int>, pair<int,int>>> q;

	q.push(make_pair(make_pair(0, 0), make_pair(0,0)));
	v[0][0][0] = true;
	while (!q.empty())
	{
		int x = q.front().first.first;
		int y = q.front().first.second;
		int horse = q.front().second.first;
		int result = q.front().second.second;
		//cout << "x : " << x << "y : " << y << "horse" <<horse<<"result : "<<result<< '\n';
		if (x == (H - 1) && y == (W - 1))
			return result;
		q.pop();
		//말처럼 뛰기
		if (horse < K)
		{
			for (int k = 0; k < 8; ++k)
			{
				int newX = x + horsex[k];
				int newY = y + horsey[k];
				//cout << newX << " " << newY << '\n';
				if (0 <= newX && newX < H && 0 <= newY && newY < W && v[newX][newY][horse+1] == false && MAP[newX][newY] !=1)
				{
					q.push(make_pair(make_pair(newX, newY),make_pair(horse+1, result+1)));
					v[newX][newY][horse+1] = true;
				}
			}
		}
		//말처럼 안뛰기
		for (int k = 0; k < 4; ++k)
		{
			int newX = x + dx[k];
			int newY = y + dy[k];

			if (0 <= newX && newX < H && 0 <= newY && newY < W && v[newX][newY][horse] == false && MAP[newX][newY] != 1)
			{
				q.push(make_pair(make_pair(newX, newY), make_pair(horse, result + 1)));
				v[newX][newY][horse] = true;
			}
		}
	}
	return -1;
}


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

	Input();
	cout<<Solve();
	
	
	return 0;
}

---

6. 후기

3차원 배열 == 어렵습니다.