質問する

code

/*
김태훈 강사님 코드 인용
S -> D
*는 물

내가 가진 의문점
-> 각 bfs 가지마다 그래프를 매개변수로 저장해야할까?
-> 하나의 그래프를 사용하면 되겠구나
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int r, c;
char graph[50][51];
typedef pair<int, int> pii;
pii ddg; // 두더지 위치
vector<pii> water; // 물 위치
pii bieber; // 비버위치(도착점)

int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };

int bfs() {
    // que
    queue<pii> water_que, ddg_que;
    // visited
    int water_vt[50][50] = { 0, }, ddg_vt[50][50] = { 0, };

    // 물 que,visited
    for (int i = 0; i < water.size(); i++) {
        pii cur_water = water[i];
        water_que.push(cur_water);
        water_vt[cur_water.first][cur_water.second] = 1;
    }
    // 두더지 que,visited
    ddg_que.push(ddg);
    ddg_vt[ddg.first][ddg.second] = 1;

    // 물과 두더지를 탐색하면서 갈수있는지 판단
    // 두더지가 비버의 굴을 탐색하면 거리를 출력하고 종료
    // 두더지가 더이상 탐색못하면 KAKTUS 출력하고 종료
    while (!ddg_que.empty()) {
        // 물 이동
        int water_que_size = water_que.size(); // 현재 숫자만큼만 큐 반복
        for (int i = 0; i < water_que_size; i++) {
            pii cur_water = water_que.front();
            water_que.pop();
            // 상하좌우
            for (int idx = 0; idx < 4; idx++) {
                int my = cur_water.first + dy[idx], mx = cur_water.second + dx[idx];
                // 범위
                if (my < 0 || my >= r || mx < 0 || mx >= c) continue;
                // 방문 가능한지 체크
                if (graph[my][mx] != 'D' && graph[my][mx] != 'X' && water_vt[my][mx] == 0) {
                    // 다음 이동
                    water_vt[my][mx] = water_vt[cur_water.first][cur_water.second] + 1;
                    water_que.push(pii(my, mx));
                }
            }
        }

        // 두더지 이동
        int ddg_que_size = ddg_que.size();
        for (int i = 0; i < ddg_que_size; i++) {
            pii cur_ddg = ddg_que.front();
            ddg_que.pop();
            for (int idx = 0; idx < 4; idx++) {
                int my = cur_ddg.first + dy[idx], mx = cur_ddg.second + dx[idx];
                // 범위
                if (my < 0 || my >= r || mx < 0 || mx >= c) continue;
                // 방문 가능한지 체크
                if (graph[my][mx] != 'X' && water_vt[my][mx] == 0 && ddg_vt[my][mx] == 0) {
                    // 종료점 체크
                    if(pii(my,mx)==bieber) return ddg_vt[cur_ddg.first][cur_ddg.second];
                    // 다음 이동
                    ddg_vt[my][mx] = ddg_vt[cur_ddg.first][cur_ddg.second] + 1;
                    ddg_que.push(pii(my, mx));
                }
            }
        }
    }
    return -1;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        cin >> graph[i];
    }

    // 위치 저장
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (graph[i][j]=='S') ddg = pii(i, j);
            if (graph[i][j] == '*') water.push_back(pii(i, j));
            if (graph[i][j] == 'D') bieber = pii(i, j);
        }
    }

    int ans = bfs();
    if (ans == -1) cout << "KAKTUS" << endl;
    else cout << ans << endl;
    return 0;
}