[BOJ/Gold 4] 백준 29703 펭귄의 하루(C++)

문제 링크

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

29703번: 펭귄의 하루

 

문제

 1 × 1 크기의 정사각형 칸으로 각각 나누어져 있는 N × M의 행렬로 표현되는 펭귄 마을이 있다. 펭귄 마을의 정보는 문자 'S', 'H', 'E', 'D', 'F'로 나타난다. E는 천적이 없어 펭귄이 이동해도 괜찮은 안전 구역을 나타내며, D는 펭귄의 천적인 바다표범이 살고 있어 펭귄이 이동할 수 없는 위험 구역을 나타낸다. 그리고 F는 펭귄이 먹이를 구할 수 있는 물고기 서식지를 의미한다.

펭귄 마을에서 펭귄은 위험 구역이 아닌 곳을 상하좌우로 이동한다. 단, 펭귄은 멸종위기 동물이기 때문에 멸종 위기 동물 보호 구역인 펭귄 마을 밖으로는 이동할 수 없다.

펭귄이 현재 위치에서 출발하여 물고기 서식지 중 최소한 한 곳을 들러 사냥을 마치고 집으로 돌아가려 한다. 펭귄이 사냥하는 데 걸리는 시간은 고려하지 않으며 출발 지점에서 먼저 물고기들이 서식하는 구역을 들르지 않았더라도 펭귄이 사는 집을 지나갈 수 있다. 또한, 물고기들이 서식하는 구역을 들른 후에 펭귄이 출발한 지역을 거쳐 펭귄의 집으로 돌아갈 수 있다. 펭귄 마을에서 한 칸을 이동하는 데 1초가 걸린다고 할 때, 물고기를 사냥해 최대한 빠르게 펭귄의 집에 도달하는 데 걸리는 시간을 구해보자.

 

입력

첫째 줄에는 펭귄 마을의 세로 길이 N(1 ≤ N ≤ 1,000)과 가로 길이 M(1 ≤ M ≤ 1,000)이 주어진다.

둘째 줄부터 N개의 줄에 펭귄 마을의 위치 정보를 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 S, H, E, D, F로 이루어져 있고, 아래와 같은 의미를 가진다.

• S: 펭귄의 현재 위치
• H: 펭귄의 집
• E: 안전 구역
• D: 위험 구역
• F: 물고기 서식지

펭귄의 현재 위치와 펭귄의 집은 공간에 1개만 있으며 물고기 서식지는 공간에 1개 이상 1,000개 이하로 존재한다.

 

출력

펭귄이 물고기 서식지를 들러 집에 도착할 때 걸리는 최소 시간을 출력한다. 만약, 펭귄이 물고기 서식지를 들러 집에 도착할 수 없다면 −1을 출력한다.

 

예제 입력 1

5 3
SEE
EFE
HEE
EEE
EEE

예제 출력 1

4

예제 입력 2

3 3
SDF
DDE
EEH

예제 출력 2

-1

 

알고리즘 분류

• 그래프 탐색

 

풀이

물고기는 한 마리만 잡아도 되므로, 물고기를 잡으면 이미 방문했던 구역도 다시 방문할 수 있도록 방문을 기록하는 배열을 3차원 배열 Visited[Y][X][K]로 선언한다.

그리고 시작 지점에서 BFS를 수행하여 물고기를 잡고 집으로 돌아갈 때 BFS를 종료한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 1001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M;
int MAP[MAX][MAX];
queue<pair<pair<int, int>, pair<int, int> > > Q;
bool Visited[MAX][MAX][2];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };

void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        string S;
        cin >> S;
        for (int j = 0; j < M; j++) {
            if (S[j] == 'S') {
                Q.push(make_pair(make_pair(i, j), make_pair(0, 0)));
                Visited[i][j][0] = true;
            }
            else if (S[j] == 'H') {
                MAP[i][j] = 2;
            }
            else if (S[j] == 'D') {
                MAP[i][j] = -1;
            }
            else if (S[j] == 'F') {
                MAP[i][j] = 1;
            }
        }
    }
}

int BFS() {
    while (!Q.empty()) {
        int NowY = Q.front().first.first;
        int NowX = Q.front().first.second;
        int NowT = Q.front().second.first;
        int NowF = Q.front().second.second;
        Q.pop();

        if ((NowF == 1) && (MAP[NowY][NowX] == 2)) {
            return NowT;
        }

        for (int i = 0; i < 4; i++) {
            int NextY = NowY + MoveY[i];
            int NextX = NowX + MoveX[i];
            if ((NextY >= 0) && (NextY < N) && (NextX >= 0) && (NextX < M) && !Visited[NextY][NextX][NowF] && (MAP[NextY][NextX] != -1)) {
                if (NowF == 0) {
                    if (MAP[NextY][NextX] == 1) {
                        Q.push(make_pair(make_pair(NextY, NextX), make_pair(NowT + 1, 1)));
                        Visited[NextY][NextX][1] = true;
                    }
                    else {
                        Q.push(make_pair(make_pair(NextY, NextX), make_pair(NowT + 1, 0)));
                        Visited[NextY][NextX][0] = true;
                    }
                }
                else {
                    Q.push(make_pair(make_pair(NextY, NextX), make_pair(NowT + 1, 1)));
                    Visited[NextY][NextX][1] = true;
                }
            }
        }
    };

    return -1;
}

void find_Answer() {
    cout << BFS() << "\n";
}

int main() {
    FASTIO
    input();
    find_Answer();

    return 0;
}