글 읽기 - C언어 BFS로 구현하였습니다. 혹시 통과하지 못하는 테스트 케이스가 있을까요??

khk6748 6년 전 0

C언어 BFS로 구현하였습니다. 혹시 통과하지 못하는 테스트 케이스가 있을까요??

이전 질문에서 나온 케이스들도 잘 통과해서요! 질문드립니다.

#include<stdio.h>
#include<stdlib.h>

#define MAX 100

int main(void)
{
    int M, N, head, tail, x, y, i, j, div;
    char str[MAX+4];
    
    scanf("%d %d", &N, &M);
    int miro[N][M];
    
    for (i=0;i<N;i++){
        scanf("%s",str);
        div = atoi(str); //string to int
        
        for (j=0;j<M;j++){
            miro[i][M-1-j] = div % 10;
            div = div/10;
        }
    }
    
    int que[N*M + 1][2];
    
    //Init Queue
    head = 0;
    tail = 0;
    que[tail][0] = 0; //start x
    que[tail][1] = 0; //start y
    tail++;
    miro[0][0] = 0; // visited

    while (head < tail){
        //POP
        x = que[head][0];
        y = que[head][1];
        head++;

        if (x-1 >=0 && miro[x-1][y] == 1){
            miro[x-1][y] = miro[x][y] + 1;
            //PUSH
            que[tail][0] = x-1;
            que[tail][1] = y;
            tail++;
        }
        if (y-1 >=0 && miro[x][y-1] == 1){
            miro[x][y-1] = miro[x][y] + 1;
            //PUSH
            que[tail][0] = x;
            que[tail][1] = y-1;
            tail++;
        }
        if (x+1 < N && miro[x+1][y] == 1){
            miro[x+1][y] = miro[x][y] + 1;
            //PUSH
            que[tail][0] = x+1;
            que[tail][1] = y;
            tail++;

            if (x+1 == N-1 && y == M-1) break;
        }
        if (y+1 < M && miro[x][y+1] == 1){
            miro[x][y+1] = miro[x][y] + 1;
            //PUSH
            que[tail][0] = x;
            que[tail][1] = y+1;
            tail++;
            
            if (x == N-1 && y+1 == M-1) break;
        }
        miro[x][y] = 0; // visited
        
        /*
        // Check miro
        for (i=0;i<N;i++){
            for (j=0;j<M;j++){
                printf("%d ",miro[i][j]);
            }
            printf("\n");
        }
        printf("\n");
        */
    }
    printf("%d\n",miro[N-1][M-1]+1);
    return 0;
}

djm03178 6년 전 1

이렇게 하면 이전에 갔던 곳을 재방문하고, 다시 재방문하고... 가 반복되어 큐가 터질 뿐 아니라 시간도 매우 오래 걸리게 됩니다.

이전에 방문한 곳은 다시 가지 않게 막아야 합니다.

khk6748 6년 전 0

@djm03178 님 댓글 감사합니다!
방문할 대상은 1인 값만 que에 넣게 되어있고 while 문 마지막에 방문했던 지점은 0으로 바꿔주기 때문에 재방문하지 않는다고 생각하였습니다.
check 주석을 풀어서 매 방문마다 찍어보아도 재방문하는 것은 아닌 거 같아서요!

저도 좀 더 고민해 보겠습니다!!

djm03178 6년 전 1

아 그렇군요. 그 부분을 놓쳤습니다.

문제는 그 부분이 아니라, 16번째 줄이네요.

이렇게 하면 수가 클 경우에 int 내에 다 담을 수가 없겠죠. int로는 10자리까지만 정확히 받을 수 있습니다.

khk6748 6년 전 0

@djm03178 정확히 지적하신 부분 때문이었습니다. 정말 감사합니다! scanf("%1d",&miro[i][j]); 로 입력을 받게끔 수정하니까 되네요!
감사합니다!!!

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

문제

문제

출처

ICPC

C언어 BFS로 구현하였습니다. 혹시 통과하지 못하는 테스트 케이스가 있을까요??

khk6748 6년 전 0

djm03178 6년 전 1

khk6748 6년 전 0

djm03178 6년 전 1

khk6748 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말