백준 3055 탈출

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

3055번: 탈출

#include<stdio.h>
#include<queue>
#define RSIZE 50
#define CSIZE 50
using namespace std;
char input[RSIZE][CSIZE];
int chk[RSIZE][CSIZE];
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
int R, C;
struct Data {
    int y, x, cnt;
};
queue<Data>wq;
queue<Data>q;
int ey, ex;
 
void init() {
    scanf("%d %d", &R, &C);
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf(" %1c", &input[i][j]);
            if (input[i][j] == '*') {
                chk[i][j] = 1;
                q.push({ i,j ,0 });
            }
            if (input[i][j] == 'D') {
                ey = i; ex = j;
            }
        }
    }
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (input[i][j] == 'S') {
                chk[i][j] = 1;
                q.push({ i,j,0 });
            }
        }
    }
}
void safeGo() {
 
    while (q.size() != 0) {
        Data c = q.front(); q.pop();
        if (input[c.y][c.x] == '*') {
            for (int dir = 0; dir < 4; dir++) {
                Data n = c;
                n.y += dy[dir]; n.x += dx[dir]; n.cnt++;
                if (0 <= n.y && n.y < R && 0 <= n.x && n.x < C) {
                    if (chk[n.y][n.x] == 0 && input[n.y][n.x] == '.' && input[n.y][n.x] != 'X'  && input[n.y][n.x] != 'S' && input[n.y][n.x] != 'D') {
                        input[n.y][n.x] = '*';
                        chk[n.y][n.x] = 1;
                        q.push(n);
                    }
                }
            }
        }
        if (input[c.y][c.x] == 'S') {
            for (int dir = 0; dir < 4; dir++) {
                Data n = c;
                n.y += dy[dir]; n.x += dx[dir]; n.cnt++;
                if (0 <= n.y && n.y < R && 0 <= n.x && n.x < C) {
                    if (chk[n.y][n.x] == 0 && input[n.y][n.x] != 'X' && input[n.y][n.x] != '*') {
                        input[n.y][n.x] = 'S';
                        chk[n.y][n.x] = n.cnt;
                        q.push(n);
                    }
                }
            }
        }
    }
 
}
int main(void) {
    init();
    safeGo();
    if (chk[ey][ex] == 0) {
        printf("KAKTUS\n");
    }
    else
    printf("%d\n", chk[ey][ex]);
    return 0;
}

일단 큐랑 같지만 조금 다른건 물의 위치를 큐에 먼저넣고 고슴도치의 위치를 그뒤에큐에 넣고 한큐에서

물의 위치와 고슴도치인 경우를 나누어 탐색을 진행하였습니다. 

 

물이 이동 할 수 있는 방향은

고슴도치의 이동할수 있는 방향은

위와 같이 문제의 조건에 맞추어 해주면된다. 물의 경우 일반적으로  . 이면 가능하고 X인 벽이 아니여야하고 S가 갈수 있는길 D 목적지를 넘어서는 안되기 때문에 위와같이 조건을 주었고

 

고슴도치의 경우도 X 벽이 아니여야하고 물인쪽은 못가게 설계를 하였습니다.

 

그리고 미리 저장한 D의  y, x 값을 이용하여 chk[y][x] 가 0 이라면 고슴도치가 결승점에 못들어 간것이기 때문에 

KAKTUS 를 출력하고 

그게 아니면 chk[y][x]에 저장된 값을 출력하면됩니다.

 

TMI 지만 KAKTUS가 무엇인지 찾아보았습니다.

시간 안에 못갔다고 고슴도치가 소리지는것인지 모르겠습니다.

무튼 오늘은 여기까지이고 항상 즐거운 코딩하세요.