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

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

1600번: 말이 되고픈 원숭이

bfs를 이용하여 푼 문제이다. 조금 색다른 방법을 사용해서 풀었다.

 

우선 나이트를 이동한 횟수에 따라서 좌표방문여부를 체크하였다. 즉 3차원 배열을 써서 방문여부를 체크하였다. 예를 들어 visit[3][5][2] = true이면 (3, 5)까지 이동하는데 2번 나이트처럼 이동하여 도착하였다라는 의미이다.

 

bfs는 상하좌우, 나이트이동으로 다음 칸을 탐색하고 나이트처럼 이동한 횟수가 최대 나이트이동 횟수보다 적으면 나이트이동으로 탐색이 가능하고 그 외에는 상하좌우이동만 가능하다고 구현하였다. 마지막에 최소로 걸린 시간을 출력하면 된다.

 

#include <iostream>
#include <queue>
#define MAX 201	
#define INF 987654321
using namespace std;

//x, y좌표, k는 걸린 시간, t는 나이트 이동횟수
class Point {
public:
	int x, y, k, t;
	Point(int x, int y, int k, int t) {
		this->x = x;
		this->y = y;
		this->k = k;
		this->t = t;
	}
};

int W, H, n; //가로, 세로, 정해진 횟수
int mat[MAX][MAX]; //입력 받은 좌표 정보
bool d[MAX][MAX][31] = { false, }; //x, y까지 k번의 나이트 처럼 이동해서 방문한 기록
int small = -1; //도달하는게 가장 짧게 걸리는 시간

//상하좌우
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

//나이트 이동
int kx[] = { 2,-2,1,-1,2,-2,1,-1 };
int ky[] = { 1,1,2,2,-1,-1,-2,-2 };

//bfs 구현
void bfs(int x, int y, int k, int t) {
	queue<Point> q;
	q.push(Point(x, y, k, t));
	d[x][y][0] = true;

	while (!q.empty()) {
		x = q.front().x;
		y = q.front().y;
		k = q.front().k;
		t = q.front().t;
		q.pop();

		if (x == H && y == W) { //도착점에 도달하였으면
			small = k; //도착점 시간을 반환하고
			break; //탈출
		}

		//상하좌우 이동
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (1 <= nx && nx <= H && 1 <= ny && ny <= W && mat[nx][ny] == 0 && d[nx][ny][t] == false) { //유효범위이고 빈 공간이고 t번 이동한 나이트가 방문한 적 없으면
				q.push(Point(nx, ny, k + 1, t)); //큐에 다음 위치를 시간 + 1을 하여 삽입
				d[nx][ny][t] = true; //t번 이동한 나이트를 (nx, ny)에 방문처리
			}
		}

		//나이트 이동, 나이트 최대 이동 수를 넘기지 않았다면 나이트를 이동한다.
		if (t < n) {
			for (int i = 0; i < 8; i++) {
				int nx = x + kx[i];
				int ny = y + ky[i];

				if (1 <= nx && nx <= H && 1 <= ny && ny <= W && mat[nx][ny] == 0 && d[nx][ny][t + 1] == false) { //유효범위이고 빈 공간이고 t + 1번 이동한 나이트가 방문한 적 없으면
					q.push(Point(nx, ny, k + 1, t + 1)); //큐에 다음 위치를 시간 + 1, 나이트 이동 횟수 + 1을 하여 삽입
					d[nx][ny][t + 1] = true; //t + 1번 이동한 나이트를 (nx, ny)에 방문처리
				}
			}
		}
	}
}

int main() {
	cin >> n;
	cin >> W >> H;

	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			cin >> mat[i][j];
		}
	}

	bfs(1, 1, 0, 0); //시작점에서 끝점 찾아가기

	cout << small;
}