글 읽기 - 기저사례를 달리하면 틀렸다고 나오는데 이유를 모르겠습니다

kmc04 2년 전 0

기저사례를 y == N-1 && x == N-1 로 했을때는 답이 맞는데,

만약 끝부분을 2로 설정하고

pipe[y][x] == 2 로 했을때는 답이 아니라고 나옵니다..

어째서 그런건가요? 아무리 생각해도 모르겠습니다

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#define MOD 1000000
using namespace std;

// 방법의 수가 항상 1000000보다 작거나 같으므로 0.1초안에 해결 가능

int N;
int pipe[16][16];

// 우 대각 아래
int dy[3] = {0,1,1};
int dx[3] = {1,1,0};

int result = 0;

// dir : 0 1 2(가로 대각 세로)
// y,x 위치에 있을 때 끝에 도달 하는 경우의 수 반환
// 0 1 2 빈칸 벽 도착지점
void solution(int y, int x, int dir) {
    // 틀림
    if(pipe[y][x] == 2) {
        result++;
        return;
    }
    // 맞음
    if(y == N-1 && x == N-1) {
        result++;
        return;
    }

    // 파이프가 가로일 경우
    if(dir == 0) {
        for(int i=0; i<2; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >= N || nx >= N) continue;
            if(pipe[ny][nx] == 1) continue;
            // 대각선으로 갈때 추가적인 체크
            if(i == 1 && (pipe[y+1][x] == 1 || pipe[y][x+1] == 1)) continue;
            solution(ny,nx,i);
        }
    }
    // 파이프가 대각선일 경우
    else if(dir == 1) {
        for(int i=0; i<3; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >= N || nx >= N) continue;
            if(pipe[ny][nx] == 1) continue;
            if(i == 1 && (pipe[y+1][x] == 1 || pipe[y][x+1] == 1)) continue;
            solution(ny,nx,i);
        }
    }
    // 파이프가 세로인 경우
    else if(dir == 2) {
        for(int i=1; i<3; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >= N || nx >= N) continue;
            if(pipe[ny][nx] == 1) continue;
            if(i == 1 && (pipe[y+1][x] == 1 || pipe[y][x+1] == 1)) continue;
            solution(ny,nx,i);
        }
    }
}

int main()
{
    scanf("%d",&N);
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            scanf("%d",&pipe[i][j]);
        }
    }
    pipe[N-1][N-1] = 2;
    solution(0,1,0);
    printf("%d\n",result);
}

djm03178 2년 전 1

끝 부분이 막혀있을 수 있습니다. 좌표로 검사하면 애초에 그 좌표로 가지 않겠지만, 2로 바꾸어놓으면 뚫린 것으로 처리하게 됩니다.

kmc04 2년 전 0

애초에 막혀있을 수도 있군요.. 감사합니다!

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

문제

문제

출처

ICPC

기저사례를 달리하면 틀렸다고 나오는데 이유를 모르겠습니다

kmc04 2년 전 0

djm03178 2년 전 1

kmc04 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말