글 읽기 - 3055 탈출 문제에서 테스트 케이스가 하나 더 있어야 할 것 같습니다.

cjstjdgur123 7년 전 0

채점 번호 5161854 에서 제출한 답안은 정답 처리를 받았지만,

2 3

*..

S.D

로 입력되었을 때, 오른쪽으로 곧장 두 번 이동하여 S가 D에 도달할 수 있음에도 불구하고, 불가능하다고 판정해버립니다.

따라서, 문제 테스트 케이스 중 위와 같이 처음 시작 시, 물( * )과 고슴도치( S )가 맞붙어 있음에도 불구하고, 출구( D )에 도달할 수 있는 상황을 만들어야한다고 생각합니다.

첨부한 코드는 채점 번호 5161854 코드입니다. (정답처리 받았지만 잘 못됨)

이 코드에서 56번째 줄에 있는 조건을 제거해야 위와 같은 케이스에서 제대로된 답을 출력합니다.

#include <stdio.h>

#define ROAD 0  // 아무 것도 없는 길
#define PET 1   // 고슴도치, 확장하게 되며 최단거리를 찾기 위해 물처럼 사방으로 퍼진다.
#define WATER 2 // 물, 확장하게 되며 고슴도치의 이동경로와 길을 삼켜버린다.
#define STONE 3 // 돌, 제자리에 있으나 삼켜지지 않음
#define EXIT 4  // 출구, 제자리에 있으며 삼켜지지 않고, PET이 주변에 다가오길 기다림.

#define ROW 0
#define COL 1

int R, C, map[ 50 ][ 50 ] = { 0 }, day = 0;
int endR, endC;

// r, c의 위치 주변에 what 타일이 있는지 확인한다.
int aroundCheck ( int r, int c, int what )
{
    if( c > 0 && map[r][c-1] == what ) return 1;
    if( c < C - 1 && map[r][c+1] == what ) return 1;
    if( r > 0 && map[r-1][c] == what ) return 1;
    if( r < R - 1 && map[r+1][c] == what ) return 1;
    return 0;
}

// r, c의 위치에서 level 값보다 낮은 레이어 값을 지닌 타일을 삼켜버린다.
void expand ( int r, int c, int stack[][2], int* cnt, int level )
{
    if( c > 0 && map[r][c-1] < level )
        map[r][c-1] = level, stack[*cnt][ROW] = r, stack[*cnt][COL] = c-1, (*cnt)++;
    if( c < C - 1 && map[r][c+1] < level )
        map[r][c+1] = level, stack[*cnt][ROW] = r, stack[*cnt][COL] = c+1, (*cnt)++;
    if( r > 0 && map[r-1][c] < level )
        map[r-1][c] = level, stack[*cnt][ROW] = r-1, stack[*cnt][COL] = c, (*cnt)++;
    if( r < R - 1 && map[r+1][c] < level )
        map[r+1][c] = level, stack[*cnt][ROW] = r+1, stack[*cnt][COL] = c, (*cnt)++;
}

// 재귀호출이 일어나는 계산. 매 회마다 1턴의 동작을 실행한다.
void calculate ( int waterArr[][2], int waterLength, int petArr[][2], int petLength )
{
    day++; // 1턴 증가
    
    // 출구 주변에 고슴도치가 있다면 종료.
    if( aroundCheck( endR, endC, PET ) )
        return;
    
    int stackWater[ waterLength * 4 ][ 2 ], cntWater = 0;
    int stackPet[ petLength * 4 ][ 2 ], cntPet = 0;
    
    // 물 타일을 하나씩 확장시켜준다.
    for( int i = 0; i < waterLength; ++ i )
        expand( waterArr[i][ROW], waterArr[i][COL], stackWater, &cntWater, WATER );
        
    // 고슴도치 타일을 하나씩 확장시켜준다.
    for( int i = 0; i < petLength; ++ i )
        if( map[ petArr[i][ROW] ][ petArr[i][COL] ] == PET ) // 없어야할 조건
            expand( petArr[i][ROW], petArr[i][COL], stackPet, &cntPet, PET );
    
    // cntPet이 0이라면 이번 턴에서 고슴도치가 확장한 타일이 없다는 것이다.
    // 즉, 앞으로 영영 아무 곳으로 이동할 수 없다는 뜻으로 종료한다.
    if( cntPet == 0 )
        day = -1; // day가 -1인 경우, 불가능한 상황으로 KAKTUS를 출력하도록 한다.
    else
        calculate( stackWater, cntWater, stackPet, cntPet );
        // 확장할 물, 고슴도치 타일들을 보내주며 다음 턴을 실행한다.
}

int main ( void )
{
    // 확장할 물과 고슴도치 위치를 담을 배열을 생성한다.
    int stackWater[ 2500 ][ 2 ] = { 0 }, cntWater = 0;
    int stackPet[ 1 ][ 2 ] = { 0 }, cntPet = 0;
    
    // 초기 맵을 받아오기 위한 부분
    char tmp;
    scanf( "%d %d", &R, &C );
    for( int r = 0; r < R; ++ r )
    {
        for( int c = 0; c < C; ++ c )
        {
            scanf( " %c", &tmp );
            switch( tmp )
            {
                case 'D':
                    map[ r ][ c ] = EXIT;
                    endR = r, endC = c;
                    // 출구의 경우 endR, endC로 따로 위치를 저장해둔다.
                    break;
                case '*':
                    map[ r ][ c ] = WATER;
                    stackWater[ cntWater ][ ROW ] = r;
                    stackWater[ cntWater ][ COL ] = c;
                    cntWater ++;
                    break;
                case 'S':
                    map[ r ][ c ] = PET;
                    stackPet[ cntPet ][ ROW ] = r;
                    stackPet[ cntPet ][ COL ] = c;
                    cntPet ++;
                    break;
                case 'X':
                    map[ r ][ c ] = STONE;
                    break;
            }
        }
    }
    
    // 재귀 함수를 호출한다.
    calculate( stackWater, cntWater, stackPet, cntPet );
    
    // day가 -1이라면 불가능한 상황이고, 아닐 경우 출구로 도달하기까지 최단 거리 값이다.
    if( day == -1 )
        printf( "KAKTUS" );
    else
        printf( "%d", day );
        
    return 0;
}

baekjoon 7년 전 0

추가했습니다.

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

문제

문제

출처

ICPC

3055 탈출 문제에서 테스트 케이스가 하나 더 있어야 할 것 같습니다.

cjstjdgur123 7년 전 0

baekjoon 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말