[G3] 백준 1600번 말이 되고픈 원숭이 C++ 너비 우선 탐색, 우선순위 큐, 시뮬레이션

리뷰

 

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

방향 배열을 두개 사용하고, 방문 배열을 3차원으로 사용하여 푼 문제

 

 

전역 변수

• k : 말의 움직임을 할 수 있는 횟수를 저장할 변수
• w : 맵의 가로 길이를 저장할 변수
• h : 맵의 세로 길이를 저장할 변수
• lst : 맵 정보를 저장하기 위한 2차원 배열
• v : 말의 이동을 한 횟수를 기준으로 방문 처리를 하기 위한 3차원 배열
• hx, hy : 말의 이동을 진행할 방향 배열
• dx, dy : 4방향 이동을 진행할 방향 배열
• Pos : 맵 상에서의 이동을 기록할 구조체, 이동 횟수 t를 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

int dijkstra()

 

 

너비 우선 탐색을 통해 시작점에서 목표지점까지 걸리는 최소 거리를 리턴하기 위한 함수

1. Pos타입의 우선순위 큐 pq를 초기화 해주고, 초기값 0, 0, 0, 0을 입력해 준다.
2. 초기 지점에 대해 방문처리 후 pq가 빌 때 까지 while루프를 돌아준다.
3. 매 루프마다 pq에서 요소 한개씩을 뽑아 구조체의 요소를 각각 cx, cy, ct, cs로 파싱해준다.
4. 기저 조건으로 만약 cx, cy가 맵의 오른쪽 하단에 도달했다면 ct를 리턴해 준다.
5. 4방향 탐색을 진행하고 맵의 범위 안이면서 방문처리 되지 않았고 벽이 아니라면 이동을 진행한다.
6. 이동한 위치에 방문표시 후 pq에 시간을 1 늘린 상태로 이동한 좌표를 push해준다.
7. 만약 cs가 k보다 작다면 즉, 말의 이동을 할 수 있는 상태라면
8. 8방향 탐색을 진행하고 맵의 범위 안이면서 방문처리 되지 않았고 벽이 아니라면 이동을 진행한다.
9. 이동한 위치에 방문표시 후 pq에 시간을 1, 말 이동 횟수를 1늘린 상태로 이동한 좌표를 push해준다.
10. 만약 while루프가 종료될 때까지 최소값을 찾지 못했다면 -1을 리턴해 준다.

 

문제풀이

• k, w, h값을 입력 받고 h * w크기의 맵 정보를 입력 받아 lst배열에 저장해 준다.
• dijkstra함수를 호출한 뒤 리턴 값을 출력해 준다.

 

트러블 슈팅

1. 예제도 모두 맞았고 로직 상 특이 사항이 확인되지 않았으나 제출 하자마자 틀렸습니다를 받았다.
2. 문제를 다시 잘 읽어보니 K값의 범위가 0이상 30이하의 정수임을 확인했다.
3. 따라서 v배열의 범위를 30에서 31로 늘려주었더니 바로 AC를 받았다.

 

참고 사항

실제로 다익스트라를 사용하진 않았으니 함수명은 bfs가 맞는 것 같다.

문제를 설계할때  말의 이동을 한 횟수를 기준으로 방문 처리를 해야 특이 사항이 없을 것이라 판단했다.

예를 들어 이동 횟수 기준으로 오름차순만 한 경우 아래같은 경우에는 체크할 수 없다는 생각이 들었다.

1
4 4
0 0 1 1
1 0 1 1
1 0 1 1
1 1 1 0

 

위의 경우 바로 말의 움직임을 써버려서 (2, 1)로 이동했다면 이미 방문 처리가 되어 있기 때문에 걸어서 갈 수 없다.

따라서 현재까지 사용한 말의 움직임을 기준으로 방문 배열을 사용해 주었다.

 

정답 코드

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

int k, w, h;
int lst[200][200];
int v[31][200][200];
int hx[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int hy[] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
struct Pos {
	int x, y, t, s;
	bool operator<(const Pos& other) const {
		return t > other.t;
	}
};

int dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ 0, 0, 0, 0 });
	v[0][0][0] = 1;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, ct = pos.t, cs = pos.s;
		if (cx == h - 1 && cy == w - 1) return ct;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < h && 0 <= ny && ny < w && !v[cs][nx][ny] && !lst[nx][ny]) {
				v[cs][nx][ny] = 1;
				pq.push({ nx, ny, ct + 1, cs });
			}
		}

		if (cs < k) {
			for (int i = 0; i < 8; ++i) {
				int nx = cx + hx[i], ny = cy + hy[i], ns = cs + 1;
				if (0 <= nx && nx < h && 0 <= ny && ny < w && !v[ns][nx][ny] && !lst[nx][ny]) {
					v[ns][nx][ny] = 1;
					pq.push({ nx, ny, ct + 1, ns });
				}
			}
		}
	}
	return -1;
}

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

	cin >> k >> w >> h;
	for (int i = 0; i < h; ++i)
		for (int j = 0; j < w; ++j)
			cin >> lst[i][j];

	cout << dijkstra();
}