글 읽기 - 알고리즘 자체에 대한 질문입니다.

imgosari 6년 전 0

시간초과가 아니고 틀렸습니다가 계속 나와서 처음 질문을 올리게 되었습니다. (_ _) 코드 한 번 봐주시길 바라요!

제 솔루션은 이렇습니다.
. 으로시작된 부분을 모두 deque에 저장(queue 1번이라고 가정)한 뒤, deque에서 하나씩 빼면서 탐색을 시작합니다.
탐색 방법 : 백트래킹을 이용하여 'O'에 도달할 때 까지 경로를 저장합니다. 그 순간, 초기에 저장한 deque 1번의 요소를 모두 돌면서 'O'에 도달할 때 까지 나아간 경로를 적용하여, 모든 경로에 부합하는지 판단합니다.
예외처리 : 1) 'O'에 도달하였지만, 탐색 횟수가 11이 넘는다면 그 경로는 유망하지 않으므로

2) 현재의 탐색 횟수가 11이 넘는다면 더 이상 탐색하지 않습니다.

#include <stdio.h>
#include <memory.h>
#include <deque>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
int TC,N,M,ans,dx[4]={0,1,0,-1},dy[4]={-1,0,1,0},ei,ej;
char cdir[4]={'U','R','D','L'},m[11][11];
deque< pair<int, int> > hoobo;
deque<char> dirq;
pair<int, int> go(int y, int x, int dir)
{
    while(true)
    {
        if(m[y+dy[dir]][x+dx[dir]]=='#') break;
        else if(m[y+dy[dir]][x+dx[dir]]=='O')
        {
            if(dir==0) return {y-1,x};
            else if(dir==1) return {y,x+1};
            else if(dir==2) return {y+1,x};
            else return {y,x-1};
        }
        else if(m[y+dy[dir]][x+dx[dir]]=='.')
        {
            x+=dx[dir];
            y+=dy[dir];
        }
    }
    return {y,x};
}
int isans() // 현재의 경로가 모든 '.'에서 정답으로 갈 수 있는지 확인합니다.
{
    deque< pair<int, int> > tq(hoobo);
    while(!tq.empty())
    {
        int mans=0;
        int y=tq.front().first;
        int x=tq.front().second;
        deque<char> tdir(dirq);
        while(!tdir.empty())
        {
            pair< int, int > tans;
            char d=tdir.front();
            if(d=='U') tans=go(y,x,0);
            else if(d=='R') tans=go(y,x,1);
            else if(d=='D') tans=go(y,x,2);
            else tans=go(y,x,3);
            if(tans.first==ei&&tans.second==ej)
            {
                mans=1;
                break;
            }
            y=tans.first;
            x=tans.second;
            tdir.pop_front();
        }
        if(!mans) return 0;
        tq.pop_front();
    }
    return 1;
}
void dfs(int dir, int cnt, int i, int j)
{
    if(cnt>10||ans) return;
    for(int d=0;d<4;d++)
    {
        if(cnt!=1&&abs(d-dir)==2) continue;
        pair<int, int> pp=go(i,j,d);
        if(pp.first==ei&&pp.second==ej)
        {
            dirq.push_back(cdir[d]); // 정답으로 도달한 마지막 경로를 저장합니다.
            if(!isans())
            {
                dirq.pop_back(); // 정답이 아니면 마지막 경로를 뺍니다.
                continue;
            }
            else
            {
                if(cnt<=10) // 횟수가 10 이하인 경우에만 정답으로 출력합니다.
                {
                    ans=1;
                    while(!dirq.empty())
                    {
                        printf("%c",dirq.front());
                        dirq.pop_front();
                    }
                    printf("\n");
                    return;
                }
                else return;
            }
        }
        else if((pp.first!=i||pp.second!=j))
        {
            dirq.push_back(cdir[d]); //deque 백트래킹.
            dfs(d,cnt+1,pp.first,pp.second);
            if(ans) return; // 정답이 나왔다면 탈출합니다.
            dirq.pop_back();
        }
    }
    return;
}
int main()
{
    scanf("%d",&TC);
    while(TC--)
    {
        ans=0;
        memset(m,0,sizeof(m));
        deque< pair<int, int> > empty;
        swap(hoobo, empty);
        scanf("%d %d",&N,&M);
        char t[11];
        for(int i=0;i<N;i++)
        {
            scanf("%s",&t);
            int len=strlen(t);
            for(int j=0;j<len;j++)
            {
                m[i][j]=t[j];
                if(t[j]=='.') hoobo.push_back({i,j}); // '.'인 좌표를 탐색의 후보로 정합니다.
                else if(t[j]=='O')
                {
                    ei=i;
                    ej=j;
                }
            }
        }
        int out=0;
        deque< pair<int,int> > hoobot(hoobo);
        while(!hoobot.empty()) // 모든 '.' 좌표를 탐색합니다.
        {
            int gi=hoobot.front().first;
            int gj=hoobot.front().second;
            for(int d=0;d<4;d++)
            {
                dfs(d,1,gi,gj);
                if(ans) break;
            }
            if(out) break;
            hoobot.pop_front();
        }
        if(!ans) printf("XHAE\n"); // 정답을 한번도 못 구한 경우입니다.
    }
}

zlzmsrhak 6년 전 2

반례입니다.

코드를 보면, 93~99번째 줄에서 구슬은 항상 움직여야 한다는 조건이 있습니다.

저 경우 "답은 있지만, 답대로 움직인 경우 구슬이 어느 위치에 있던 한번이라도 멈추는 경우"는 답이 나오지 않습니다.

1
7 7
#######
O.##..#
#.....#
##.#.##
#..#..#
##.#.##
#######

imgosari 6년 전 0

그렇네요.. 제가 dfs 돌리는 과정에서 제자리에 멈추게 되면 그 다음으로 아무데도 못가게 막아놨네요...

유망하지 않다고 판단하는 과정에서 논리상의 오류가 있었던 것 같습니다.

정말 감사합니다. 반례 찾기가 코드 짜는 것 보다 더 힘든데..

많은 도움이 되었습니다.

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

문제

문제

출처

ICPC

알고리즘 자체에 대한 질문입니다.

imgosari 6년 전 0

zlzmsrhak 6년 전 2

imgosari 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말