[BOJ] 백준 1600번 말이 되고픈 원숭이 C++

문제

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

1600번: 말이 되고픈 원숭이

골드4 BFS 문제이다. 문제를 이해하고, 접근하는 것 자체는 쉬웠는데 메모리초과, 시간초과 때문에 좀 힘들었던 문제이다.

풀이

첫번째로 말처럼, 원숭이처럼 이동할 수 있는 방향 배열을 만들어주었다. 그리고 tuple을 통해 x, y좌표와 현재 말처럼 이동할 수 있는 횟수(능력)을 Queue에 담아주었다. 이후 (0,0,0)부터 BFS를 돌면된다. 

하지만 어떻게 BFS를 돌릴건지 잘 생각하여야한다. 꼭 말처럼 이동하는 상황이 먼저 나올 필요는 없다. 원숭이처럼 이동하다 말처럼 이동해도 되는 것이고, 말처럼 이동하지 않아도 된다. 이를 잘 고려하여 문제에 접근해보면 현재 말처럼 이동할 수 있는 횟수(moveCnt)가 원숭이의 잠재력(k)을 넘지 않는다면 모든 방향(말, 원숭이)에 대해 Queue에 넣어주면 되는 것이고, 잠재력을 이미 다 사용했다면 원숭이처럼 이동할 수 있는 방향에 대해서만 Queue에 넣어주면 된다. 

추가로 말처럼 이동하였다면 능력을 한 번 사용한 것이므로 현재 말처럼 이동할 수 있는 횟수(moveCnt)를 1증가 시킨 형태로 dist배열과 Queue에 넣어주면 된다.

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>

using namespace std;

int k, n, m;
int moveCnt = 0;
int board[201][201];
//최소 동작횟수 저장 배열
int dist[201][201][31];
int dx[12] = { 1,0,-1,0,-2,-1,1,2,2,1,-1,-2 };
int dy[12] = { 0,1,0,-1,-1,-2,-2,-1,1,2,2,1 };
bool canGo;
//tuple -> x좌표, y좌표, 말처럼 이동한 횟수
queue<tuple<int, int, int>> q;

void reset()
{
	for (int k = 0; k < 31; k++)
	{
		for (int i = 0; i <= n; i++)
		{
			for (int j = 0; j <= m; j++)
			{
				dist[i][j][k] = -1;
			}
		}
	}
}

void bfs()
{
	q.push({0, 0, 0});
	dist[0][0][0] = 0;

	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();
		int moveCnt = get<2>(cur);

		//목적지 도착시 출력하고 리턴
		if (get<0>(cur) == n - 1 && get<1>(cur) == m - 1)
		{
			cout << dist[n - 1][m - 1][moveCnt];
			canGo = true;
			return;
		}

		if (moveCnt < k)
		{
			for (int dir = 4; dir < 12; dir++)
			{
				int nx = get<0>(cur) + dx[dir];
				int ny = get<1>(cur) + dy[dir];
				
				//범위 나감 -> out
				if (nx < 0 || nx >= n || ny < 0 || ny >= m)
				{
					continue;
				}
				//장애물이 있음, 이미 방문함 -> out
				if (board[nx][ny] == 1 || dist[nx][ny][moveCnt + 1] != -1)
				{
					continue;
				}
				
				q.push({ nx, ny, moveCnt + 1 });
				dist[nx][ny][moveCnt + 1] = dist[get<0>(cur)][get<1>(cur)][moveCnt] + 1;
			}
		}
		
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = get<0>(cur) + dx[dir];
			int ny = get<1>(cur) + dy[dir];

			//범위 나감 -> out
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
			{
				continue;
			}
			////장애물이 있음, 이미 방문함 -> out
			if (board[nx][ny] == 1 || dist[nx][ny][moveCnt] != -1)
			{
				continue;
			}

			q.push({ nx, ny, moveCnt });
			dist[nx][ny][moveCnt] = dist[get<0>(cur)][get<1>(cur)][moveCnt] + 1;
		}
	}
}

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

	cin >> k >> m >> n;

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

	//동작횟수 저장 배열 초기화
	reset();
	
	bfs();

	if (!canGo)
	{
		cout << -1;
	}
}

 

시간초과났던 코드

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

using namespace std;

int k, n, m;
int moveCnt = 0;
int board[201][201];
//최소 동작횟수 저장 배열
int dist[201][201][31];
int dx[12] = { 1,0,-1,0,-2,-1,1,2,2,1,-1,-2 };
int dy[12] = { 0,1,0,-1,-1,-2,-2,-1,1,2,2,1 };
bool canGo;
//tuple -> x좌표, y좌표, 말처럼 이동한 횟수
queue<tuple<int, int, int>> q;

void reset()
{
	for (int k = 0; k < 31; k++)
	{
		for (int i = 0; i <= n; i++)
		{
			for (int j = 0; j <= m; j++)
			{
				dist[i][j][k] = -1;
			}
		}
	}
}

void bfs()
{
	q.push({0, 0, 0});
	dist[0][0][0] = 0;

	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();
		int moveCnt = get<2>(cur);

		//목적지 도착시 출력하고 리턴
		if (get<0>(cur) == n - 1 && get<1>(cur) == m - 1)
		{
			cout << dist[n - 1][m - 1][moveCnt];
			canGo = true;
			return;
		}

		//12방향에 대해 검사하면서 (0 ~ 3 -> 원숭이처럼 이동, 4 ~ 11 -> 말처럼 이동)
		for (int dir = 0; dir < 12; dir++)
		{
			bool check = false;

			int nx = get<0>(cur) + dx[dir];
			int ny = get<1>(cur) + dy[dir];

			//범위 나감 -> out
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
			{
				continue;
			}
			//장애물이 있음 -> out
			if (board[nx][ny] == 1)
			{
				continue;
			}

			//이미 방문했음 -> out
			for (int cnt = 0; cnt <= moveCnt; cnt++)
			{
				if (dist[nx][ny][cnt] != -1)
				{
					check = true;
				}
			}
			if (check)
			{
				continue;
			}
			
			//말처럼 이동한 횟수가 K보다 같거나 많아 원숭이처럼만 이동 가능
			if (moveCnt >= k)
			{
				if (dir < 4)
				{
					q.push({ nx, ny, moveCnt });
					dist[nx][ny][moveCnt] = dist[get<0>(cur)][get<1>(cur)][moveCnt] + 1;
				}
			}
			//말처럼 이동 가능한 상태임
			else
			{
				//원숭이처럼 이동했음 -> moveCnt는 증가하지 않고 최소동작횟수만 업데이트 해줌
				if (dir < 4)
				{
					q.push({ nx, ny, moveCnt});
					dist[nx][ny][moveCnt] = dist[get<0>(cur)][get<1>(cur)][moveCnt] + 1;
				}
				//말처럼 이동했음 -> moveCnt를 1증가 시킨채로 업데이트해줌
				else
				{
					q.push({ nx, ny, moveCnt + 1 });
					dist[nx][ny][moveCnt + 1] = dist[get<0>(cur)][get<1>(cur)][moveCnt] + 1;
				}
			}	
		}
	}
}

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

	cin >> k >> m >> n;

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

	//동작횟수 저장 배열 초기화
	reset();
	
	bfs();

	if (!canGo)
	{
		cout << -1;
	}
}