백준 말이 되고픈 원숭이(1600) C++ 풀이

알고리즘 분류

그래프 이론

그래프 탐색

너비 우선 탐색(BFS)

문제 해결 아이디어

 BFS를 이용하여 K의 값이 0보다 크면 현 위치에서 말의 움직임으로 갈 수 있는 곳을 체크하여 Queue에 넣는다. 그 다음 상하좌우로 갈 수 있는 곳을 체크 한 후 Queue에 넣어, 최종적으로 도착지점에 도달하면 Cost를 출력한다.

코드

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

int k;
int map[201][201];
bool visited[201][201][31];
int w, h;
// 상하좌우 움직임
int dirX[4] = { -1,1,0,0 };
int dirY[4] = { 0,0,-1,1 };
// 말의 움직임
int horseX[8] = { -1,-1,1,1,-2,-2,2,2 };
int horseY[8] = { -2,2,-2,2,-1,1,-1,1 };


int bfs()
{
	// [좌표(X,Y), (cost,k)]
	queue <pair<pair<int, int>, pair<int,int>>> q;

	// 방문 처리
	visited[0][0][k] = 1;
	// (0,0)부터 시작
	q.push(make_pair(make_pair(0, 0), make_pair(0,k)));

	// Queue가 비워있지 않는 동안 반복
	while (!q.empty())
	{
		// x좌표
		int x = q.front().first.first;
		// y좌표
		int y = q.front().first.second;
		// cost
		int c = q.front().second.first;
		// k의 값
		int _k = q.front().second.second;


		q.pop();

		// 도착지점 도착
		if (x == w - 1 && y == h - 1) return c;

		// K가 0보다 크면 말 움직임도 체크하기
		if (_k > 0)
		{
			for (int i = 0; i < 8; i++)
			{
				int _x = horseX[i] + x;
				int _y = horseY[i] + y;

				if (_x >= 0 && _x < w && _y >= 0 && _y < h)
				{
					if (map[_y][_x] == 0 && !visited[_y][_x][_k - 1])
					{
						visited[_y][_x][_k - 1] = true;
						q.push(make_pair(make_pair(_x, _y), make_pair(c + 1, _k - 1)));
					}
				}
			}
		}

		// 상하좌우 움직임
		for (int i = 0; i < 4; i++)
		{
			int _x = dirX[i] + x;
			int _y = dirY[i] + y;

			if (_x >= 0 && _x < w && _y >= 0 && _y < h)
			{
				if (map[_y][_x] == 0 && !visited[_y][_x][_k])
				{
					visited[_y][_x][_k] = true;
					q.push(make_pair(make_pair(_x, _y), make_pair(c + 1,_k)));
				}
			}
		}
	}

	// 도착지점에 도달 할 수 없다면
	return -1;
}

int main()
{
	cin >> k;
	cin >> w >> h;

	// 갈 수 있는 곳(0), 갈 수 없는 곳(1)
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			cin >> map[i][j];
		}
	}

	// BFS를 하여 값 저장
	int num = bfs();

	cout << num;
}

코드 설명

상하좌우의 값과 말의 움직임 값을 배열에 넣은 후, k값에 따라 queue에 좌표, cost, k의 값을 넣으면 된다. 여기서 중요한 점은 k마다 방문했는가?를 다르게 체크하기 때문에 visited를 3차원 배열로 사용하여 [y][x][k]로 사용하였다. 만약 queue가 다 비워도 도착지점에 도달하지 못하면 도착지점에 갈 수 없기 때문에 -1를 출력하면 된다.