[BEAKJOON] 3055_탈출_C언어

https://www.acmicpc.net/problem/3055

Ah....재밌는 문제였으나......나한테는 너무 어렵게 접근한 나머지.........꽤 많은 시간을 소비하고..내 정답률도 많이 떨어뜨린 문제였다.

조만간 다시 풀어봐야지!!!!

풀이

최단거리를 구하는 문제이므로 당연히!!!BFS를 이용해야 될 것 같다. 그래서 BFS로 접근하여 문제를 풀었다.

내 풀이에서 일반적인 BFS 문제들과 다른 점이 두 가지가 있다.

1. 물이 퍼져나가는 것에 대한 BFS와 고슴도치의 이동에 대한 BFS, 총 BFS를 2번 사용해야 된다는 것.

2. 물은 퍼져나가고 고슴도치는 길을 찾기 위해 탐색하는데 물과 두더지의 BFS를 무조건 한 차례씩 돌아가면서 돌리는 것이 아니라 물과 고슴도치 모두 BFS를 수행하면서 같은 층에 존재하는 큐를 모두 사용하고 차례를 넘겨야 된다는 것이다.(뒤에 예제를 보면 이해하기가 쉬울듯,,,)

전체적인 흐름.

1. 입력을 받고 *와 S는 각각 큐에 저장한다.

2. 초기 S의 위치는 변수 x,y에 저장한다.

3. 반복문을 통하여 탐색을 시작한다.

1)변수 x,y값 상하좌우에 D가 존재하면 현재 단계 +1의 값을 출력

2)물을 퍼뜨린다.

(고슴도치를 먼저 이동시키는게 맞으나 먼저 물을 퍼트리고 이동 못하게 해도 된다고 생각하여..)

3)고슴도치를 이동시킨다. 이때 고슴도치의 마지막 탐색 위치의 상하좌우중 D가 존재하면 현재 위치값을 변수 x,y에 저장.

예외로는 탐색 도중에 헛도는 부분을 탐색 불가능이라 판단하여 KAKTUS를 출력하였다.

제일 왼쪽이 처음 화면이며, 두번째 세번째가 반복문안에서 같이 돌아간다.

제일 오른쪽 그림 2위에 D가 존내하므로 이 위치를 x,y에 저장하여 물이 퍼지기전에 +1하여 출력해준다.

*참고*

추가 적인 테스트케이스를 원하시는 분들은

http://hsin.hr/coci/archive/2006_2007/

로 들어가셔서 CONTEST #1의 테스트 케이스를 다운받아 'slikar'폴더안의 파일들로 테스트하시면 됩니다.

제출한 코드

#include <stdio.h>
int map[60][60];
int water_Q[250000][2];//0 : row(x), 1: column(y)
int S_Q[250000][2];//0 : row, 1: column
int water[250000];
int S[250000];
int S_front = -1, S_back = -1, water_front = -1, water_back = -1, R, C, water_num, S_num,y,x;
//S_front S_Q의 front/S_back S_Q의 백, water_front water_Q의 front, water_back water_Q의 back, water_num  water_Q의 BFS 단계를 나타냄, S_num S_Q의 BFS단계를 나타냄
//y x는 비버집 직전으 좌표.
int dx[4] = { 0,0,-1,1 }, dy[4] = { -1,1,0,0 };
 
void input();
int main()
{
    input();
    x = S_Q[0][0]; y = S_Q[0][1];
 
    while (S_front != S_back||water_front != water_back)
    {
        if (map[y+1][x] == 'D'|| map[y-1][x] == 'D'|| map[y][x+1] == 'D'|| map[y][x-1] == 'D')
        {
            printf("%d\n",S[S_front+1]);
            return 0;
        }
        water_num++;
        while (water[water_front+1] <= water_num)
        {
            water_front++;
            if (water[water_front] == 0)
            {
                break;
            }
            for (int i = 0; i < 4; i++)
            {
                int water_x = water_Q[water_front][0] + dx[i];
                int water_y = water_Q[water_front][1] + dy[i];
                if (map[water_y][water_x] != 'S' && map[water_y][water_x] != 0 && map[water_y][water_x] != 'D'&&map[water_y][water_x]!='X'&&map[water_y][water_x] != '*')
                {
                    map[water_y][water_x] = '*';//물이 퍼져나감
                    water_Q[++water_back][1] = water_y;//큐에 넣어요
                    water_Q[water_back][0] = water_x;//큐에 넣어요
                    water[water_back] = water[water_front] + 1;////BFS 단계 증가
                }
            }
        }
        S_num++;
 
        while (S[S_front + 1] <= S_num)//두더지 BFS시작!!
        {
            S_front++;
            if (S[S_front] == 0)//S_back이 쌓이지 않고 S_front만 증가하면 더이상 움직일 곳이 없는 곳으로 판단. 종료
            {
                printf("KAKTUS\n");
                return 0;
            }
            for (int i = 0; i < 4; i++)
            {
                int S_x = S_Q[S_front][0] + dx[i];
                int S_y = S_Q[S_front][1] + dy[i];
                if (map[S_y][S_x] == '.'&& map[S_Q[S_front][1]][S_Q[S_front][0]] != '*'&&map[S_y][S_x] != 'X')
                {
                    map[S_y][S_x] = 1;
                    S_Q[++S_back][1] = S_y;
                    S_Q[S_back][0] = S_x;
                    S[S_back] = S[S_front] + 1;
 
                    if (map[S_y + 1][S_x] == 'D' || map[S_y - 1][S_x] == 'D' || map[S_y][S_x + 1] == 'D' || map[S_y][S_x - 1] == 'D')//지금 좌표가 비버집 직전인지 확인
                    {
                        y = S_y;
                        x = S_x;
                    }
                }
 
            }
        }
    }
    printf("KAKTUS\n");
    return 0;
}
 
void input()//입력받는 함수
{
    scanf("%d %d", &R, &C);
    getchar();
    for (int i = 1; i <= R; i++)//R
    {
        for (int j = 1; j <= C; j++)//C
        {
            scanf("%c", &map[i][j]);
            if (map[i][j] == '*')
            {
                water_Q[++water_back][0] = j;
                water_Q[water_back][1] = i;
                water[water_back] = 1;
            }
            else if (map[i][j] == 'S')
            {
                S_Q[++S_back][0] = j;
                S_Q[S_back][1] = i;
                S[S_back] = 1;
                map[i][j] = 'S';
            }
        }
        getchar();
    }
}

#백준 #알고리즘 #C언어 #3055탈출 #백준3055탈출