[BOJ/Silver 1] 백준 31946 죽음의 등굣길(C++)

문제 링크

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

 

문제

지훈이는 등굣길에서 보도블록을 지날 때 같은 색의 보도블록만을 밟으면서 이동한다. 왜냐하면 다른 색의 보도블록을 밟으면 사망하기 때문이다.

등굣길은 𝑁 × 𝑀 크기의 행렬로 표현할 수 있으며 행렬의 각 원소는 하나의 보도블록으로 이루어져 있다. 지훈이는 1행 1열에서 출발해 𝑁행 𝑀열에 도착해야 한다.

빨간색 또는 회색으로 이루어진 등굣길을 이동하면서 지훈이는 현재 밟고 있는 보도블록과 같은 색의 보도블록만을 밟고 이동해야 한다. 또한 지훈이의 점프력이 𝑋이기 때문에 맨해튼 거리가 𝑋 이하인 보도블록으로만 이동할 수 있다. 지훈이가 무사히 등교를 마칠 수 있는지 알려주자.

 

입력

첫째 줄에 등굣길의 행의 개수 𝑁이 주어진다. (2 ≤ 𝑁 ≤ 100)

둘째 줄에 등굣길의 열의 개수 𝑀이 주어진다. (2 ≤ 𝑀 ≤ 100)

셋째 줄부터 𝑁개의 줄에 걸쳐 𝑖 + 2번째 줄에 𝑖번째 행의 보도블록의 색깔을 나타내는 𝑀개의 정수가 열 순서대로 공백으로 구분되어 주어진다. 0인 경우 빨간색 보도블록, 1인 경우 회색 보도블록이라는 것을 의미한다.

마지막 줄에 지훈이의 점프력을 나타내는 정수 𝑋가 주어진다. (1 ≤ 𝑋 ≤ 10)

 

출력

지훈이가 살아서 등교에 성공할 수 있으면 ALIVE, 그렇지 않으면 DEAD를 출력한다.

 

예제 입력 1

2
3
0 0 0
0 0 0
1

예제 출력 1

ALIVE

예제 입력 2

2
2
0 0
0 1
5

예제 출력 2

DEAD

 

출발 지점과 도착 지점의 색이 다르기 때문에 살아서 등교할 수 없다.

 

노트

 𝑥1행 𝑦1열에 있는 보도블록과 𝑥2행 𝑦2열에 있는 보도블록 사이의 맨해튼 거리는 |𝑥1 − 𝑥2| + |𝑦1 − 𝑦2|로 정의한다.

 

알고리즘 분류

• 그래프 탐색

 

풀이

현재 보도블록에서 맨해튼 거리 내에 있는 모든 보도블록을 탐색하면서 현재 보도블록의 색깔과 동일한 보도블록만을 큐에 넣는다.

그렇게 가능한 모든 보도블록을 탐색하면서 N행 M열까지 도달할 수 있다면 ALIVE, 도달할 수 없다면 DEAD를 출력한다.

 

코드

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

using namespace std;
int N, M, X;
int MAP[MAX][MAX];
bool Visited[MAX][MAX];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };
int ManhattanY[4] = { 1,1,-1,-1 };
int ManhattanX[4] = { -1,1,1,-1 };

void input() {
    cin >> N;
    cin >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> MAP[i][j];
        }
    }
    cin >> X;
}

bool bfs() {
    queue<pair<int, int> > Q;
    Q.push(make_pair(0, 0));
    Visited[0][0] = true;

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

        if ((NowY == (N - 1)) && (NowX == (M - 1))) {
            return true;
        }

        for (int i = 1; i <= X; i++) {
            for (int j = 0; j < 4; j++) {
                int NextY = NowY + (MoveY[j] * i);
                int NextX = NowX + (MoveX[j] * i);
                
                for (int k = 0; k < i; k++) {
                    int NNextY = NextY + (ManhattanY[j] * k);
                    int NNextX = NextX + (ManhattanX[j] * k);
                    if ((NNextY >= 0) && (NNextY < N) && (NNextX >= 0) && (NNextX < M) && !Visited[NNextY][NNextX] && (MAP[NNextY][NNextX] == MAP[NowY][NowX])) {
                        Q.push(make_pair(NNextY, NNextX));
                        Visited[NNextY][NNextX] = true;
                    }
                }
            }
        }
    };

    return false;
}

void find_Answer() {
    if (bfs()) {
        cout << "ALIVE\n";
    }
    else {
        cout << "DEAD\n";
    }
}

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

    return 0;
}