글 읽기 - 서브태스크 1만 맞아서 질문드립니다

cdt416z 4년 전 0

백트래킹으로 문제를 풀었는데

visit배열 초기화도 DFS함수 내에서 자체적으로 해서 따로 시행할 필요 없게 만들었고

한번이라도 모든 배열을 다 돌았을 시에는 즉시 return해서 불필요한 반복도 없으며

배열의 행 열이 둘다 홀수이며 시작 위치의 x, y를 더한 값이 홀수이면 바로 IMPOSSIBLE을 출력하도록 설계했습니다

여기서 더 줄일 수 있을까요?

백트래킹이 아니라면 어떤 알고리즘을 쓰면 좋을지 문의드립니다 ㅠㅠ

#include <stdio.h>

int visit[101][101];
int di[4] = {1, -1, 0, 0};
int dj[4] = {0, 0, 1, -1};
int T, R, C, r, c;
char result[10010];

int DFS(int num, int i, int j){
    int res = 0;
    if(num == R * C - 1){
        for(int k = 0; k < num; k++){
            printf("%c", result[k]);
        }
        puts("");
        return 1;
    }
    for(int k = 0; k < 4; k++){
        int ni = i + di[k];
        int nj = j + dj[k];
        if(ni < 1 || ni > R || nj < 1 || nj > C){
            continue;
        }
        if(visit[ni][nj] == 1){
            continue;
        }
        visit[ni][nj] = 1;
        switch(k){
            case 0: result[num] = 'D';
                break;
            case 1: result[num] = 'U';
                break;
            case 2: result[num] = 'R';
                break;
            case 3: result[num] = 'L';
                break;
        }
        res = DFS(num + 1, ni, nj);
        if(res == 1){
        	visit[ni][nj] = 0;
            return 1;
        }
        visit[ni][nj] = 0;
    }
    return res;
}

int main(){
    scanf("%d", &T);
    for(int p = 0; p < T; p++){
        scanf("%d %d %d %d", &R, &C, &r, &c);
        if(R % 2 == 1 && C % 2 == 1 && (r + c) % 2 == 1){
        	printf("IMPOSSIBLE\n");
        }
        else{
        	visit[r][c] = 1;
            if(!DFS(0, r, c)){
                printf("IMPOSSIBLE\n");
            }
            visit[r][c] = 0;
        }
    }
    return 0;
}

cdt416z 4년 전 0

@jh05013 갑작스럽게 언급해서 죄송합니다

이 문제 정답자가 jh05013님밖에 없어서..

혹시 시간이 허용된다면 어떻게 더 효율적으로 만들 수 있는지 한수 부탁드립니다

jh05013 4년 전 0

가능한 경로가 너무 많아서 백트래킹으로 다 볼 수는 없습니다. 조건을 만족하는 경로를 직접 만들어내야 하며, 그런 경로가 없을 필요충분조건도 알아내어야 합니다.

minjae200 4년 전 0

이해력이 부족해서...조건을 만족하는 경로를 직접 만든다는것이 백트래킹을 이용해서 만들어야 된다는 것인가요???

jh05013 4년 전 1

백트래킹 없이 손으로(?) 직접 만들어야 합니다. 수학 문제 풀듯이 하면 됩니다. 예를 들어 R = 1이라면, 백트래킹을 하지 않아도 어떻게 풀어야 하는지 쉽게 알 수 있습니다.

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

문제

문제

출처

ICPC

서브태스크 1만 맞아서 질문드립니다

cdt416z 4년 전 0

cdt416z 4년 전 0

jh05013 4년 전 0

minjae200 4년 전 0

jh05013 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말