글 읽기 - 문제를 잘못 해석한것인지... 질문을 보면서 무엇이 문제 인지 모르겠습니다..

hahawjstk 5년 전 0

제가 생각했을 때는 재귀가 끝나면서 자동으로 해결해준다고 생각했는데 완전히 동작이 다르게 돌아가는 것 같아요....

혹시 어떤 것이 문제일까요?ㅠㅠㅠㅠㅠ

다른 질문들을 읽어봐도 왜 이렇게 작동하는지 모르겠어요ㅠㅠ

밑에 코드에서 저의 결과와 다른 분의 해답을 적어 봤습니다...

저의 결과값은 59가 나오고 실제 문제 해답은 57이 나옵니다.

***저의 결과
 1  1  1  1  1  1  1  1  1  1 
 1 30 31 32 34 35 36 37 38  1 
 1 29 28 33  1  1  1  1 39  1 
 1 26 27  1  1 51 52 41 40  1 
 1 25  1  1 53 49 48 42 43  1 
 1 23 24 12 11 50 46 45 44  1 
 1 22 14 13 10  9 47  1 54  1 
 1 16 15  2  1  8  1  1 55  1 
 1 17 18  3  4  7  1  1 56  1 
 1 21 19 20  5  6 59 58 57  1 
 1  1  1  1  1  1  1  1  1  1 
    
***질문에서 본 해답
 0  0  0  0  0  0  0  0  0  0
 0 56 57 46 45 44 43 42 41  0
 0 55 48 47  0  0  0  0 40  0
 0 50 49  0  0 36 37 38 39  0
 0 51  0  0 35 34 31 30  0  0
 0 52 53 12 11 33 32 29 28  0
 0 54 14 13 10  9  0  0 27  0
 0 16 15  2  1  8  0  0 26  0
 0 17 18  3  4  7  0  0 25  0
 0 21 19 20  5  6 22 23 24  0
 0  0  0  0  0  0  0  0  0  0


#include <cstdio>

using namespace std;

int N,M;
int sy,sx,dir,cnt;
int map[54][54];
bool visited[54][54];

//0은 북, 1은 동, 2은 남, 3은 서
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};

bool isposs(int y, int x){
    return x >= 0 && y >= 0 && x < M && y < N;
}

void dfs(int y, int x, int dir){
    cnt++;
    map[y][x] = cnt;
    int nextDir = dir;
    for(int i = 0 ; i < 4 ; i++){
        nextDir = nextDir < 1 ? 3 : nextDir - 1;
        int xx = x + dx[nextDir];
        int yy = y + dy[nextDir];
        
        if(isposs(yy,xx) && map[yy][xx] == 0){
            dfs(yy, xx, nextDir);
        }
    }
}

void printMap(){
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < M ; j++){
            printf("%2d " , map[i][j]);
        }
        puts("");
    }
    puts("");
}

int main() {
    freopen("input.txt","r",stdin);
    scanf("%d %d", &N, &M);
    scanf("%d %d %d", &sy, &sx, &dir);
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < M ; j++){
            scanf("%d", &map[i][j]);
        }
    }
    dfs(sy, sx, dir);
    printf("%d\n", cnt);
    printMap();   
}

luniro 5년 전 1

21번에서 2-4까지 돌고나면 왼쪽을 바라보게 됩니다 이 상태에서 한 칸 후진하면 19번으로 가게되고 주변이 청소되어 있으므로 한 칸 후진하여 20번 위치로 이동합니다

이런 식으로 이동하다보면 6번의 오른쪽 위치에 도달하게 됩니다

일반적으로는 dfs와 같이 움직이지만 깊게 들어갔을때는 dfs에서 탈출해서 후진하면서 새로 dfs를 돌려야합니다

hahawjstk 5년 전 0

@luniro

아아아아아아!!!!

왔던 길을 다시 가는 것이 아니라 그냥 그 방향을 가지고 후진을 진행한다는 것이..... 감사합니다!!!!

다시 한번 작성해보도록 해보겠습니다!!!

정말 감사합니다!!

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

문제

문제

출처

ICPC

문제를 잘못 해석한것인지... 질문을 보면서 무엇이 문제 인지 모르겠습니다..

hahawjstk 5년 전 0

luniro 5년 전 1

hahawjstk 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말