글 읽기 - 테스트 케이스 14개를 넣어봤지만 어디가 틀린지 모르겠습니다.

jaeseb96 4년 전 0

제 나름대로 질문게시판의 테스트케이스를 14개를 모아서 테스트를 해봤지만 문제가 없는데 어디서 틀린것인지 모르겠습니다 ㅠㅠㅠ

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <tuple>
#include <iostream>
#include <unistd.h>
#include <stdbool.h>
#include <stdlib.h>

using namespace std;

int N, M;
int arr[1004][1004]={0,};
int dir[4][2] {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

void BFS(void);

// input1 : 15
// input2 : -1
// input3 : 29
// input4 : 1
// input5 : 20
// input6 : 10
// input7 : 6
// input8 : 3
// input9 : 13
// input10 : 5
// input11 : 7
// input12 : 39
// input13 : 18
// input14 : 5

int main(void)
{
    //freopen(argv[1], "r", stdin);
    scanf("%d %d\n", &N, &M);

    for (int i=0; i<=N+1; i++)
        for (int j=0; j<=M+1; j++)
            arr[i][j]=-1;

    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++)
            scanf("%1d", &arr[i][j]);

    BFS();

    return 0;
}

void BFS(void)
{
    int depth=0;
    bool visited[N+1][M+1][2]={0,};

    queue <tuple<int, int, int> > q;

    q.push(make_tuple(1, 1, 0));
    visited[1][1][0]=1;

    while (!q.empty()) {
        depth++;
        if (get<0>(q.front()) == N && get<1>(q.front()) == M) {
            printf("%d\n", depth);
            break;
        }
        int size = q.size();

        for (int s=0; s<size; s++) {
            for (int i=0; i<4; i++) {
                int a=dir[i][0] + get<0>(q.front());
                int b=dir[i][1] + get<1>(q.front());

                if (!get<2>(q.front())) {
                    if (arr[a][b]==0 && !visited[a][b][0]) {
                        q.push(make_tuple(a, b, 0));
                        visited[a][b][0]=1;
                    }
                    if (arr[a][b]==1 && !visited[a][b][0]) {
                        q.push(make_tuple(a, b, 1));
                        visited[a][b][1]=1;
                    }
                }
                else {
                    if (arr[a][b]==1)
                        continue;
                    if (arr[a][b]==0 && !visited[a][b][1] && !visited[a][b][0]) {
                        q.push(make_tuple(a, b, 1));
                        visited[a][b][1]=1;
                    }
                }
            }
            q.pop();
        }
    }

    if (!visited[N][M][0] && !visited[N][M][1])
        printf("-1\n");
}

djm03178 4년 전 0

배열의 인덱스 범위 검사가 전혀 이루어지지 않고 있습니다.

jaeseb96 4년 전 0

73번째 줄에

if (!(0<a && a<=N && 0<b && b<=M))

continue;

를 추가했는데도 안되는데,, 제가 인덱스 범위 검사를 잘못한건가요?

djm03178 4년 전 1

몇 가지 문제점이 더 보이네요.

63번째 줄에서만 마지막에 도달했는지를 검사하면, 같은 시간 내에 도달할 수 있는 좌표들 중 큐에 가장 앞에 있던 게 아니라면 출력이 이루어지지 않습니다. 예를 들어 69번째 줄의 루프가 돌던 중간에 (N,M) 좌표가 있다면 어떻게 될까요?
79번째 줄은 (a, b, 1)을 방문해야 할지를 체크하는 조건문이니까, if문에서도 !visited[a][b][1] 이 되어야 합니다.
87번째 줄도 (a, b, 1)을 방문해야 할지를 체크하는 조건문이니까, && !visited[a][b][0]는 필요 없습니다.

jaeseb96 4년 전 0

첫번째는 생각도 못했네요,, 감사합니다 !!

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

문제

문제

출처

ICPC

테스트 케이스 14개를 넣어봤지만 어디가 틀린지 모르겠습니다.

jaeseb96 4년 전 0

djm03178 4년 전 0

jaeseb96 4년 전 0

djm03178 4년 전 1

jaeseb96 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말