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

mch473700

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

7-B

7-B 이 방식은 완탐방식일까요?

작성

360

수정됨

http://boj.kr/a788644d92fe4bc5bb99fe02b91e1f46

항상 감사드립니다. 문제 풀기 전 최대 3가지방향과 16개의 범위로 3^16 이겠거니 완탐은 불가능하겠다. 생각하고 문제를 풀기 시작했는데요..

막상 풀고 선생님 코드를 보니 제 코드는 완전탐색으로 푼것같은 느낌이 들어서 질문드립니다.

사실 시간초과가 나야 정상인 코드가 아닌가 싶어 질문드립니다.

c++코딩-테스트

답변 2

mch473700

질문자

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

혹시

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

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

큰돌

지식공유자

안녕하세요 mch님 ㅎㅎ

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

>> 이부분 설명 수정하겠습니다...

최대 시간 복잡도는 3^(2n - 1) 이 됩니다.

이 문제를 봤을 때 어떠한 경로가 있을까? 라고 생각해보면 아래로 내려가는 경로밖에 없음을 알 수 있습니다. 위로 올라가지는 않죠.

세로 - 가로로 이동하게 되면 2n의 경로를 가지고

대각선으로만 이동하게 되면 n 의 경로를 가지는 것을 알 수 있습니다.

다만

1.문제 처음 조건인 가로짜리 하나 놓아져있다.

2.선을 기반으로 파이프를 놓는게 아니라 격자안에다가 넣는다.

이런 것들은 일단 제외하고 말씀드릴게요.

이 경로에서 어떠한 방법으로 갈건지를 결정해야 하는 것이고 최대 3^2n이 되는 것이죠.

다만, 문제 조건을 보면 가로 -> 세로가 바로 안되기 때문에 가로 - 세로 안에는 대각선이 들어가야 하는 게 자명합니다. 그렇다고 하면 3^(n - 1) ~ 3^(2n - 1) 사이가 됩니다. 대각선 하나만 들어가는 경우는 3^(2n - 1)이 되겠죠. 즉, 최대 시간복잡도는 경로가 가장 긴 3^(2n - 1)이 됩니다.

그러나... 이 문제를 풀 때 이렇게 복잡하게 들어갈 필요는 없습니다.

각 격자당 상태값은 3개이기 때문에

3^(n*n)이 됩니다.

하지만 이를 DP로 만들게 되면

n x n x 3이 되는 것이죠.

해당 정점이 어떻게 끝나느냐 : 가로 또는 세로, 대각선 이러한 상태값을 중심으로 그 상태값에서 경우의 수 + 해가면서 결과를 만들어내는 것이니까요.

제가 답변을 잘 드렸어야 했는데 저도 좀 착각해가지고... 혼란을 드려 죄송합니다.

또 질문있으시면 질문주세요 ㅎㅎ

감사합니다.

mch473700

질문자

아하 그렇군요 오늘도 하나 얻어갑니다 감사합니다 선생님

큰돌

지식공유자

안녕하세요 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님 코드는 메모이제이션도 없고 딱 완탐인데... 흐으음..

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