백준[baekjoon] 27469

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

27469번: 퀸 움직이기

[문제설명]

- N행 M열로 구성된 체스판의 정보와 퀸의 시작 좌표와 도착 좌표가 주어진다.

- 체스판 각 칸에는 장애물(#)이 있거나 빈 칸(.)으로 구성되어 있다.

- 퀸은 8방향(상하좌우, 대각선)으로 장애물이 없을경우 거리 제한없이 이동가능하다.

- 두 번 연속으로 같은 방향으로 움직일 수 없다.

- 시작 좌표로 부터 K번 이동하였을 때 도착 좌표로 이동할 수 있는 경우의 수를 구해야 한다.

 

[문제풀이]

- N,M,K의 제한범위가 100밖에 되지않아 상태를 배열에 저장가능하다 생각되어 dp문제라고 생각이 들었습니다.

- dp[y][x][cnt][dir] : 직전 방향은 dir이며 (y,x)좌표를 cnt번 움직여서 이동할 수 있는 경우의수로 식을 설계하였습니다.

 

- 위 식의 시간복잡도를 O(N*M*K*8)이라고 생각되어 탑다운으로 풀어 제출하였으나 TL이 발생하였습니다. ㄴㅇㄱ

- 다시 생각해보니 (y,x)좌표 직전방향은 정해졌지만 장애물 없을경우 직전좌표와 현재좌표의 최대 거리는 D임으로 시간복잡도는 O(D*N*M*K*8)이라 TL이 발생합니다..

- 전처리가 필요해보여 탑다운에서 바텀업으로 수정하였습니다.

 

- dp식이 채워지는 모양을 잘 보면 

$dp[y][x][cnt][dir] =\sum_{d = 1}^{}{dp[y - d*dy[dir]][x - d*dx[dir]][cnt-1][dir]}$

이전 상태의 dp값을 연속적으로 더하는 구조임을 알 수 있습니다.

 

- 현재 좌표가 (y,x)일 때 직전 좌표가 (y,x-2)이라면 (y,x-1)또한 직전 좌표가 될 수 있습니다.

- 따라서 cnt번 이동에 따른 dp식을 구하기 전에 cnt-1번 이동에 따른 dp식을 8방향에 따른 누적합을 전처리해줍니다.

$dp[y][x][cnt-1][dir] =\sum_{d = 1}^{}{dp[y - d*dy[dir]][x - d*dx[dir]][cnt-1][dir]}$

- 직전 8방향 뿐만 아니라 직전 모든 방향을 더한 경우의 수를 보관한다면 두 번 연속 같은 방향으로 움직일 수 없는 제한사항을 쉽게 해결가능합니다.

 

[코드]

#include<bits/stdc++.h>

using namespace std;

const int MAX_N = 1e2;
const int DIR = 8;
const int MOD = 998244353;

int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};

int n, m, k;
int sy, sx, ey, ex;
int dp[MAX_N][MAX_N][MAX_N + 1][DIR + 1];
char board[MAX_N][MAX_N];

bool OOB(int y, int x)
{
	return y<0 || y>=n || x<0 || x>=m;
}

int getY(int y, int dir) {
	return (dir < 5 ? y : n-1-y);
}

int getX(int x, int dir) {
	return ((dir+1)%DIR < 4 ? x : m-1-x);
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);
	
	cin >> n >> m >> k;
	for(int i=0; i<n; ++i) for(int j=0; j<m; ++j) {
		cin >> board[i][j];
	}

	cin >> sy >> sx;
	cin >> ey >> ex;

	sy--; sx--;
	ey--; ex--;

	if(k == 1 && (sy == ey && sx == ex)) {
		cout << 0 << '\n';
		return 0;
	}

	dp[sy][sx][0][DIR] = 1;
	for(int dir=0; dir<DIR; ++dir) {
		dp[sy][sx][0][dir] = 1;
	}
	
	for(int cnt=1; cnt<=k; ++cnt) {
		for(int y=0; y<n; ++y) for(int x=0; x<m; ++x) {
			for(int dir=0; dir<DIR; ++dir) {
				int cy = getY(y, dir);
				int cx = getX(x, dir);
				int ny = cy + dy[dir];
				int nx = cx + dx[dir];

				if(OOB(ny, nx) || board[cy][cx] == '#' || board[ny][nx] == '#') continue;

				dp[ny][nx][cnt-1][dir] += dp[cy][cx][cnt-1][dir];
				dp[ny][nx][cnt-1][dir] %= MOD;

				dp[ny][nx][cnt-1][DIR] += dp[cy][cx][cnt-1][dir];
				dp[ny][nx][cnt-1][DIR] %= MOD;
			}
		}

		for(int y=0; y<n; ++y) for(int x=0; x<m; ++x) {
			if(board[y][x] == '#') continue;

			for(int dir=0; dir<DIR; ++dir) {
				int py = y - dy[dir];
				int px = x - dx[dir];

				if(OOB(py, px) || board[py][px] == '#') continue;

				dp[y][x][cnt][dir] = (dp[py][px][cnt-1][DIR] - dp[py][px][cnt-1][dir] + MOD) % MOD;

				dp[y][x][cnt][DIR] += dp[y][x][cnt][dir];
				dp[y][x][cnt][DIR] %= MOD;
			}
		}
	}

	cout << dp[ey][ex][k-1][DIR] << '\n';
	return 0;
}