인프런 커뮤니티 질문&답변

아 제가 질문을 잘못드렸네요 제 코드가 완탐인 것 같아서 확인차 질문했었습니다 역시나 완탐이었군요 DP로 다시 풀어보겠습니다.

혹시

격자판의 크기가 n x n이므로, 이동하는 것을 고려하면 -> 대각선으로 이동할 때 최소값인 2n-1입니다. 하지만, 실제로는 가로 또는 세로로만 이동하는 경로도 고려해야 하므로, 경로의 최대 길이는 2n보다 클 수 있습니다. 그래서 얼추... 3^32가 되는 것이죠.

이 부분이 이해가 잘 안갑니다 ㅜㅜ 혹시 추가 설명이 가능할까요?

안녕하세요 mch님 ㅎㅎ

일단 제코드는 완탐이 아니라 DP이긴 합니다.

#include <bits/stdc++.h>
using namespace std;   
void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);   
}  
int n, a[24][24], dp[24][24][3];
bool check(int y, int x, int d){
    if(d == 0 || d == 2){
        if(!a[y][x]) return true; 
    }else if(d == 1){
        if(a[y][x] == 0 && a[y - 1][x] == 0 && a[y][x - 1] == 0) return true; 
    }
    return false; 
}
int main(){
    fastIO();
    cin >> n; 
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> a[i][j];
        }
    }
    dp[1][2][0] = 1; 
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(check(i, j + 1, 0))dp[i][j + 1][0] += dp[i][j][0];
            if(check(i + 1, j + 1, 1))dp[i + 1][j + 1][1] += dp[i][j][0]; 

            if(check(i + 1, j, 2))dp[i + 1][j][2] += dp[i][j][2];
            if(check(i + 1, j + 1, 1))dp[i + 1][j + 1][1] += dp[i][j][2]; 
            
            if(check(i, j + 1, 0))dp[i][j + 1][0] += dp[i][j][1];
            if(check(i + 1, j, 2))dp[i + 1][j][2] += dp[i][j][1];
            if(check(i + 1, j + 1, 1))dp[i + 1][j + 1][1] += dp[i][j][1];  
        }
    }   
    int ret = dp[n][n][0]; 
    ret += dp[n][n][1]; ret += dp[n][n][2];  
    cout << ret << "\n"; 
    return 0;
} 

mch님의 코드는 완탐입니다.

완탐과 DP의 차이는 메모이제이션의 여부입니다. 저는 dp라는 배열을 기반으로 그 이전의 경우의 수를 저장해두고 있다는 점이 차이점입니다.

int go(int y, int x, int curDir)
{
	if (y == n && x == n) return 1;

	int ret = 0;
	int temp = continueIndex(curDir);
	for (int i = 0; i < 3; ++i)
	{
		if (temp == i) continue;
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny<1 || nx<1 || ny >n || nx >n) continue;
		if (a[ny][nx]) continue;
		if (i == 1 && (a[ny][nx] || a[ny - 1][nx] || a[ny][nx - 1])) continue;

		ret += go(ny, nx, i);
	}
	return ret;
}

mch님 코드는 메모이제이션도 없고 딱 완탐인데... 흐으음..

시간 많이 잡아먹긴하지만 신기하네요 ㅎ

그리고 시간복잡도가 3^16도 아닙니다.

격자판의 크기가 n x n이므로, 이동하는 것을 고려하면 -> 대각선으로 이동할 때 최소값인 2n-1입니다. 하지만, 실제로는 가로 또는 세로로만 이동하는 경로도 고려해야 하므로, 경로의 최대 길이는 2n보다 클 수 있습니다. 그래서 얼추... 3^32가 되는 것이죠.

이거 원래는 절대 안된다고 보시면 됩니다.

mch님이 처음에 생각하신게 맞고 -> 완탐 -> 시간복잡도상 불가능

but, 이 문제 자체의 시간초과상한선이 널널해서 그런 것 같습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.