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

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

 

 

해설

출발점 부터 목적지까지의 최단 거리를 구해야하는 문제이다. 연결된 요소로 이동하는 경우 모든 가중치가 1이므로 BFS를 사용하도록 하고 BFS를 사용하면 항상 최단거리를 보장한다는 것에서 부터 시작하도록 한다.

원숭이가 K번 말처럼 움직일 수 있는데 이를 확인하기 위해서 vis배열을 3차원으로 만들어준다.

vis[행][열][말처럼 움직인 횟수]로 visited배열을 표현하여 K번 말처럼 움직일 때의 최단 거리를 계산해준다.

말처럼 움직이는 경우에 대한 조건 처리를 주의해야한다.

코드를 보면서 이해하도록 하자.

 

코드

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <stack>
#include <sstream>
#include <set>
#include <unordered_set>
#include <cmath>
using namespace std;
using ll = long long;

const int MAX = 204;
int board[MAX][MAX];
int vis[MAX][MAX][31];
int dr[12] = { 0, 1, 0, -1, -2, -1, 1, 2, 2, 1, -1, -2 };
int dc[12] = { -1, 0, 1, 0, -1, -2, -2, -1, 1, 2, 2, 1 };

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int k, mr, mc; 
	cin >> k >> mc >> mr;
	for (int i = 1; i <= mr; ++i)
		for (int j = 1; j <= mc; ++j)
			cin >> board[i][j];

	queue<tuple<int, int, int>> q;
	q.push({ 1, 1, 0 });
	vis[1][1][0] = 1;
	while (q.empty() == false)
	{
		auto now = q.front(); 
		q.pop();
		int cr = get<0>(now); int cc = get<1>(now); int ck = get<2>(now);
		for (int d = 0; d < 4; ++d)
		{
			int nr = get<0>(now) + dr[d];
			int nc = get<1>(now) + dc[d];
			int nk = get<2>(now);
			if (nr < 1 || nr > mr || nc < 1 || nc > mc) continue;
			if (board[nr][nc] == 1 || vis[nr][nc][nk] > 0) continue;
			q.push({ nr, nc, nk });
			vis[nr][nc][nk] = vis[cr][cc][ck] + 1;
		}

		for (int d = 4; d < 12; ++d)
		{
			int nr = get<0>(now) + dr[d];
			int nc = get<1>(now) + dc[d];
			int nk = get<2>(now) + 1;
			if (nr < 1 || nr > mr || nc < 1 || nc > mc || nk > k) continue;
			if (board[nr][nc] == 1 || vis[nr][nc][nk] > 0) continue;
			q.push({ nr, nc, nk });
			vis[nr][nc][nk] = vis[cr][cc][ck] + 1;
		}
	}

	int ret = 999999999;
	bool flag = false;
	for (int i = 0; i < 31; ++i)
	{
		if (vis[mr][mc][i] > 0)
		{
			flag = true;
			ret = min(ret, vis[mr][mc][i]);
		}
	}
	if (flag == false) cout << -1 << endl;
	else cout << ret - 1 << endl;

	return 0;
}

 

후기

원숭이가 말처럼 움직이는 경우를 vis배열로 표현한다는 것 자체가 낯설어서 시간이 많이 걸릴 수 있는 문제라고 생각이 든다.

골드 3이상쯤 되면 BFS나 DFS에 이런 조건들이 붙어 특정 조건을 처리를 하는 방법을 습득해야하는듯 하다.