글 읽기 - [dfs 실패 해결] 다음 조사할 행, 열 선택 관련해서 질문 드립니다.

wnsgur2179 1년 전 1

평범하게 dfs 브루트 포스로 문제를 푼것 같습니다.

그런데 45%에서 계속 틀렸습니다가 떠서 코드 한줄을 수정해서 맞췄는데 사실 잘 이해가 가지 않습니다.

함수 수행시간 최적화를 위해서, 현재 j 행 i 열에 사다리를 설치하고 재귀를 수행할 때,

다음 함수 콜에서는 j 행 i+1 열 부터 조사해도 큰 상관이 없겠다 싶었는데, 이게 영향이 있는걸로 보여 집니다.

다른분들의 풀이를 봐도 자연스럽게 현재 행의 1번 열부터 재귀를 call 하는식으로 다시 조사를 하던데 잘 이해가 가지 않습니다. 이미 1열부터 조사를 해 와서 현재 i열 을 조사하고 있는 dfs 인데 다시 1열 부터 조사를 해야하는 논리적인 이유가 궁금합니다.

고수님들 설명좀 부탁 드립니다ㅠㅠ

//45% 틀렸습니다. 경우
void dfs(int depth, int a, int b)
{
    if(game())
    {
        answer = min(answer, depth);
        return;
    }
    if(depth==3) return;
    for(int j =a; j<=h; j++)
    {
        for(int i =b ; i<n; i++)
        {
            if(ladder[j][i] == 1 ||
                ladder[j][i-1] ==1 ||
                  ladder[j][i+1] == 1 )
                  continue;
            // cout<<"set:"<<j<<" "<<i<<" depth:"<<depth<<endl;
            set_ladder(j,i,1);
            if(i+1<n)
                dfs(depth+1, j, i+1);
            else
                dfs(depth+1, j+1, 0);
            
            set_ladder(j,i,0);        
        }
    }
};

//정답 경우
void dfs(int depth, int a, int b)
{
    if(game())
    {
        answer = min(answer, depth);
        return;
    }
    if(depth==3) return;
    for(int j =a; j<=h; j++)
    {
        for(int i =b ; i<n; i++)
        {
            if(ladder[j][i] == 1 ||
                ladder[j][i-1] ==1 ||
                  ladder[j][i+1] == 1 )
                  continue;
            // cout<<"set:"<<j<<" "<<i<<" depth:"<<depth<<endl;
            set_ladder(j,i,1);
            dfs(depth+1, j, 1);
            set_ladder(j,i,0);        
        }
    }
};

sang712 1년 전 1

예를 들어서

처음으로 놓은 사다리 발판이 (1, 2)이면

다음 dfs의 for문은

1, 3 ~ n -1

2, 3 ~ n -1

3, 3 ~ n -1

과 같이 돌기 때문에 처음부터 고려해주셔야 될 것 같습니다

wnsgur2179 1년 전 0

댓글 감사합니다.

아.. 처음으로 놓인 발판이 2라면, 여기에서 뻗어 나간 dfs는 영원히 1열을 조사할수가 없군요..

멍청한 접근이었습니다. 답변 감사합니다.

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

문제

문제

출처

ICPC

[dfs 실패 해결] 다음 조사할 행, 열 선택 관련해서 질문 드립니다.

wnsgur2179 1년 전 1

sang712 1년 전 1

wnsgur2179 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말