글 읽기 - 1799 질문드려요~

algospot 8년 전 0

dfs를 '/'방향 대각선으로 진행해가며 '\' 방향을 check배열로 확인하면서

확장해갑니다.

그런데 궁금한점이

소스1에 비해 소스2는 시간이 어마어마하게 듭니다. 둘다 통과하는데..

소스2에는 flag 처리를 하여 방문안하게 하였는데..

논리상, 현재 위치에 놓을수있더라도 미래의 최적값을 위해 '안놓음'을 '항상' 고려해야 하지 않나요??

즉 소스상의 dfs(cross+1,cnt)를 항상 고려해주어야 하지 않나요 if(!flag) 일때만 해주는게 아니라...

제가 짜고도 정논리에 대해 헷갈리네요..

//소스 1
#include <stdio.h>
int N;
int d[15][15];
int check[50];
int best;
void dfs(int cross, int cnt) {
	//가지치기
	if(cnt + (2*N-1-cross) <= best) return;
	if(cross==2*N-1) {
        if(best<cnt) best=cnt;   
        return;
    }
	int x,y,flag;
    if(cross < N) {
		x=cross;
		y=0;
	} else {
		x=N-1;
		y=cross-(N-1);	
	}
	while(x>=0 && x<N && y>=0 && y<N) {			
		if(d[y][x]==1 && !check[N+(x-y)]) {
			check[N+(x-y)]=1;
			dfs(cross+1,cnt+1);
			check[N+(x-y)]=0;
		}
		x--;
		y++;
	}
	dfs(cross+1,cnt);
}
int main(void) {
    int i,j,k;
    scanf("%d",&N);
    for(i=0;i<N;i++) {
        for(j=0;j<N;j++) {
            scanf("%d",&d[i][j]);
        }
    }
    best=0;
    dfs(0,0);
    printf("%d\n",best);
    return 0;
}

//소스2
#include <stdio.h>
int N;
int d[15][15];
int check[50];
int best;
void dfs(int cross, int cnt) {
	//가지치기
	if(cnt + (2*N-1-cross) <= best) return;
	if(cross==2*N-1) {
        if(best<cnt) best=cnt;   
        return;
    }
	int x,y,flag;
    if(cross < N) {
		x=cross;
		y=0;
	} else {
		x=N-1;
		y=cross-(N-1);	
	}
	flag=0;
	while(x>=0 && x<N && y>=0 && y<N) {			
		if(d[y][x]==1 && !check[N+(x-y)]) {
			flag=1;
			check[N+(x-y)]=1;
			dfs(cross+1,cnt+1);
			check[N+(x-y)]=0;
		}
		x--;
		y++;
	}
	if(!flag) dfs(cross+1,cnt);
}
int main(void) {
    int i,j,k;
    scanf("%d",&N);
    for(i=0;i<N;i++) {
        for(j=0;j<N;j++) {
            scanf("%d",&d[i][j]);
        }
    }
    best=0;
    dfs(0,0);
    printf("%d\n",best);
    return 0;
}

orange4glace 8년 전 0

저도 풀면서 생각을 해봤는데..

알고스팟님의 소스가 어떤지는 잘 모르겠으나

저의 경우는 / 방향 사선을 DFS로 체크해나가면서 그에 해당하는 \ 부분을 visit 하도록 기록했습니다.

그러면 / 방향을 왼쪽 아래에서부터 오른쪽 위로 올라가면서 while문에서 체크할 때 (x ++, y --)

현재 상태에 놓을 수 있는 자리가 하나라도 있다면 거기에는 무조건 하나가 놓아져야 합니다.

음.. 말로 설명하기가 어렵네요.

algospot 8년 전 0

감사해요!!~

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1799 질문드려요~

algospot 8년 전 0

orange4glace 8년 전 0

algospot 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말