[ boj : 11084 ] 나이트의 염탐

www.acmicpc.net/problem/11084

11084번: 나이트의 염탐

문제 : 나이트가 움직일 수 있는 동작이 주어지고 (1,1) 에서 (r,c)까지 최단거리로 갈 수 있는 경우의 수를 구하시오

 

해설 : 아 이거 문제 잘못읽어서 엄청 해맸습니다. 1e9+9 로 나머지를 구해야 되는데 자꾸 1e9로 해가지고 ㅡ,ㅡ....;;

어쨋든 해설을 하자면 평범하게 dp + bfs 입니다.

이동한 거리는 q에 담겨져 있는 크기가 한번 끝날때 마다 count 해주면 되는거고, 경우의 수는 dp[401][401] 배열을 선언해 준다음에 전의 경우의 수를 가져오면 되겠죠

 

제 코드를 보시면 의아하게 생각하실 부분이 만약 걸음 5번째일때 (x,y) 칸에 도착을해서 경우의 수를 저장해 두고 난 후 다음 걸음걸이에 다른 칸에서 또 다시 (x,y) 칸으로 올 수 있을때 기존 정보를 초기화를 시켜주지 않고 그냥 더해버립니다. 그러면 이건 정당성이 깨지지 않는가???라고 생각하실수도 있으십니다.

 

물론 당연히 엄청 중요하게 생각해주어야 합니다. 이 문제의 특성상 굳이 기존 정보를 돌려놓아지 않아도 정답은 출력이 되지만 이는 쉽게 간과할 수 있는 오류를 범할 수 있기 때문입니다.

 

이 문제에서는 어차피 (r,c) 에 최단거리로 도착했을 경우의 수를 구하면 되는 것이니 가장 빨리 (r,c)에 도착했으면 기존 정보와는 상관없이 바로 답을 return 시켜주어 '정답'을 캐내는데는 문제가 없는 것 입니다.

다만!!! 전체 dp 배열을 출력을 해본다면 결코 모든 칸이 올바른 걸음걸이를 출력하지 않고 있다는 것을 알 수 있으실거에요.

 

그래서 제가 다른 방법을 더 추천드립니다. 바로 걸음거리와 경우의 수 이 두가지 상태배열을 따로 만들어주는 것입니다.

그래서 비교를 하는 것이죠. 이러면 기존 정보에 덮어씌우는 일은 발생하지 않습니다.

차례대로 올리도록 하겠습니다.

 

1)

#include<bits/stdc++.h>

using namespace std;

int n, m;
int dp[401][401];
int dx[] = { -2,-2,-1,1,2,2,1,-1 }, dy[] = { -1,1,2,2,1,-1,-2,-2 };
const int MOD = (int)1e9+9;

pair<int,int> bfs();

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	if (n == 1 && m == 1) {
		cout << 0 << " " << 1;
		return 0;
	}
	pair<int,int> ans=bfs();
	if (ans.first < 0)
		cout << "None";
	else
		cout << ans.first<<" "<<ans.second;
	return 0;
}
pair<int,int> bfs()
{
	int cnt = 0;
	queue<pair<int, int>> q;
	q.push({ 1,1, });
	dp[1][1] = 1;

	while (!q.empty())
	{
		int size = q.size();
		for (int s = 0; s < size; s++) {
			pair<int, int> cur = q.front();
			q.pop();

			for (int i = 0; i < 8; i++) {
				int tx = cur.first + dx[i];
				int ty = cur.second + dy[i];

				if (tx <= 0 || tx > n || ty <= 0 || ty > m)continue;

				if (dp[tx][ty] != 0)
					dp[tx][ty] = (dp[tx][ty]%MOD + dp[cur.first][cur.second]%MOD)%MOD;
				else {
					dp[tx][ty] = dp[cur.first][cur.second]%MOD;
					q.push({ tx,ty });
				}
			}
		}
		cnt++;
		if (dp[n][m] != 0)return { cnt,dp[n][m] };
	}
	return { -1,-1 };
}

2)

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int n, m;
int dp[401][401],step[401][401];
int dx[] = { -2,-2,-1,1,2,2,1,-1 }, dy[] = { -1,1,2,2,1,-1,-2,-2 };
const int MOD = (int)1e9+9;

pair<int, int> bfs();

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

	cin >> n >> m;
	memset(step, -1, sizeof(step));
	pair<int, int> ans = bfs();
	if (ans.first < 0)
		cout << "None";
	else
		cout << ans.first << " " << ans.second;
	return 0;
}
pair<int, int> bfs()
{
	int cnt = 0;
	queue<pair<int, int>> q;
	q.push({ 1,1, });
	step[1][1] = 0;
	dp[1][1] = 1;

	while (!q.empty())
	{		
		pair<int, int> cur = q.front();
		q.pop();

		if (cur.first == n && cur.second == m)return { step[cur.first][cur.second],dp[cur.first][cur.second] };
		for (int i = 0; i < 8; i++) {
			int tx = cur.first + dx[i];
			int ty = cur.second + dy[i];

			if (tx <= 0 || tx > n || ty <= 0 || ty > m || (step[tx][ty]!=-1 && step[tx][ty] < step[cur.first][cur.second]+1))continue;
						
			step[tx][ty] = step[cur.first][cur.second] + 1;
			if (dp[tx][ty] != 0)
				dp[tx][ty] = (dp[tx][ty] % MOD + dp[cur.first][cur.second] % MOD) % MOD;
			else {
				dp[tx][ty] = dp[cur.first][cur.second];
				q.push({ tx,ty });
			}
			
		}
	}
	return { -1,-1 };
}