백준 1600 [C++]

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

 

1. 풀이방법

 

- 약간은 어려워진 BFS인 것 같습니다.

 

- 체스의 나이트 처럼 이동할 수 있는 가능 횟수가 오직 K번 이므로, K번 + 나머지 횟수는 4방향탐색

 

- 을 통해 가야하는데 DFS로 구현을 할 경우 시간이 부족합니다.

 

- 그래서 BFS로 다시 짜는데, 핵심이라고 생각되는 것은 만약에 K번 중 한번을 사용하여 점프를 뛰고

 

- 바로 거기를 방문처리를 해버리면 4방향탐색을 통해 그쪽에 도착한 후 나중에 말 처럼 점프하는 사항을

 

- 고려할 수 가 없습니다.

 

- 그래서 평소 이용하는 visit 이차원 배열을 k의 수만큼 삼차원 배열로 만들어서

 

- k 중 몇번을 써서 왔는지를 확인하고 k번을 써서 i,j에 도착했을 경우 방문처리를 해줍니다.

 

- 만약 i,j로 왔는데 k를 한번도 사용하지 않고 왔다면 그 전에 i,j에 왔으나 k를 한번 써서 방문한 경우가 있어도

 

- 다시 큐로 들어가게끔 구현하였습니다.

 

 

 

2. 주의사항

 

- visit 처리

 

 

 

3. 나의코드

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

int k, w, h;
int chesspan[200][200];
bool visit[200][200][31]; //k는 0~30
int horsemovex[8] = { -1,-2,-2,-1,1,2,2,1 };
int horsemovey[8] = { -2,-1,1,2,2,1,-1,-2 };
int dx[4] = { 0,0,1,-1 }; //k번을 다 소모했을 경우
int dy[4] = { 1,-1,0,0 };
int s = 0;
int mincount = 99999999;
bool fail = false;
struct xyk {
	int x, y, kn,s;
};
queue<xyk> tmpq;

void inputs() { //1은 장애물
	cin >> k >> w >> h;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> chesspan[i][j];
		}
	}
}
bool boundcheck(int x, int y) {
	if (x >= 0 && x < h && y >= 0 && y < w) return true;
	else return false;
}
int bfs() {
	while (1) {
		int qsize = tmpq.size();
		while (qsize--) {
			if (tmpq.empty()) { fail = true; return 0; }
			int nextx = tmpq.front().x;
			int nexty = tmpq.front().y;
			int nextk = tmpq.front().kn;
			int nexts = tmpq.front().s;
			tmpq.pop();
			if (nextx == h - 1 && nexty == w - 1) { 
				return nexts; }
			if (nextk != 0) {
				for (int i = 0; i < 8; i++) {
					int tx = nextx+ horsemovex[i]; int ty =nexty+ horsemovey[i];
					if (boundcheck(tx, ty) && visit[tx][ty][nextk-1] == false && chesspan[tx][ty] != 1) {
						tmpq.push({ tx,ty,nextk - 1,nexts +1 });
						visit[tx][ty][nextk-1] = true;
					}
				}
			}
			for (int i = 0; i < 4; i++) {
				int tx2=nextx +dx[i]; int ty2 =nexty+ dy[i];
				if (boundcheck(tx2, ty2) && visit[tx2][ty2][nextk] == false && chesspan[tx2][ty2] != 1) {
					tmpq.push({ tx2,ty2,nextk,nexts +1 });
					visit[tx2][ty2][nextk] = true;
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	tmpq.push({ 0,0,k,0 });
	//출발점은 0,0 도착점은 h-1,w-1
	int r=bfs();
	if (fail == true) { cout << -1 << "\n"; }
	else cout <<r << "\n";


	return 0;
}