[BOJ/Gold 4] 백준 25689 고속의 무작위 숫자 탐색(C++)

문제 링크

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

25689번: 고속의 무작위 숫자 탐색

 

문제

5 x 5 크기의 보드가 주어진다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있다. 보드의 격자에는 -1, 0, 1, 2, 3, 4, 5, 6, 7중 하나의 수가 적혀 있다. 격자의 위치는 (r, c)로 표시한다. r은 행 번호, c는 열 번호를 나타낸다. 행 번호는 맨 위 위치가 0이고 아래 방향으로 1씩 증가한다. 열 번호는 맨 왼쪽 위치가 0이고 오른쪽으로 1씩 증가한다. 즉, 맨 왼쪽 위 위치가 (0, 0), 맨 아래 오른쪽 위치가 (4, 4)이다. -1이 적혀 있는 칸으로는 이동할 수 없고 0, 1, 2, 3, 4, 5, 6, 7이 적혀 있는 칸으로는 이동할 수 있다.

현재 한 명의 학생이 (r, c) 위치에 있고 한 번의 이동으로 상, 하, 좌, 우 방향 중에서 한가지 방향으로 한 칸 걸어갈 수 있다. 또한 학생은 한 번의 이동으로 상, 하, 좌, 우 방향 중에서 한가지 방향으로 -1이 적혀 있는 칸을 만나거나 보드의 밖으로 벗어나서 이동할 수 없을 때까지 뛰어갈 수 있다. 단, 뛰어가는 중에 7이 적혀 있는 칸을 만나면 이동을 끝내고 해당 칸에서 멈춘다. 뛰어가다가 멈추기 전까지 중간에 지나가는 칸은 방문하지 않은 것으로 간주한다. 걸어가는 동작과 뛰어가는 동작 모두 1회 이동으로 생각한다. 학생이 현재 위치 (r, c)에서 시작하여 1, 2, 3, 4, 5, 6이 적혀 있는 칸을 순서에 상관없이 모두 방문하려고 한다. 보드에는 1, 2, 3, 4, 5, 6이 적혀 있는 칸이 1개씩 존재하고 1, 2, 3, 4, 5, 6이 적혀 있는 칸을 여러 번 방문할 수 있다. 학생이 현재 위치 (r, c)에서 시작하여 1, 2, 3, 4, 5, 6이 적혀 있는 칸을 순서에 상관없이 모두 방문하는 최소 이동 횟수를 출력하자. 학생이 현재 위치 (r, c)에서 시작하여 1, 2, 3, 4, 5, 6이 적혀 있는 칸을 모두 방문할 수 없는 경우 -1을 출력한다.

입력

첫 번째 줄부터 다섯 개의 줄에 걸쳐 보드의 각 칸에 적혀있는 수가 순서대로 주어진다. i번째 줄의 j번째 수는 보드의 (i - 1)번째 행, (j - 1)번째 열에 적혀있는 수를 나타낸다. 보드의 각 칸에 적혀 있는 수는 -1, 0, 1, 2, 3, 4, 5, 6, 7중 하나이다.

다음 줄에 학생의 현재 위치 r, c가 빈칸을 사이에 두고 순서대로 주어진다.

출력

학생이 현재 위치 (r, c)에서 시작하여 1, 2, 3, 4, 5, 6이 적혀 있는 칸을 순서에 상관없이 모두 방문하는 최소 이동 횟수를 출력한다. 학생이 현재 위치 (r, c)에서 시작하여 1, 2, 3, 4, 5, 6이 적혀 있는 칸을 모두 방문할 수 없는 경우 -1을 출력한다.

제한

• 0 ≤ r, c ≤ 4
• 학생의 현재 위치 (r, c)에는 0이 적혀 있다.
• 1, 2, 3, 4, 5, 6이 적혀 있는 칸이 1개씩 주어진다.

예제 입력 1

0 7 1 0 0
0 0 2 0 0
0 0 3 0 0
0 0 4 0 0
0 0 5 6 -1
4 1

예제 출력 1

6

(4, 1) -> (4, 3) -> (4, 2) -> (3, 2) -> (2, 2) -> (1, 2) -> (0, 2)가 최소 이동이다.

예제 입력 2

0 0 0 -1 1
0 0 0 -1 3
0 7 0 6 2
0 0 0 -1 4
0 0 0 -1 5
4 1

예제 출력 2

8

(4, 1) -> (2, 1) -> (2, 4) -> (1, 4) -> (0, 4) -> (4, 4) -> (3, 4) -> (2, 4) -> (2, 3)이 최소 이동이다.

예제 입력 3

0 0 -1 1 0
0 0 -1 2 0
0 0 -1 3 0
0 0 -1 4 0
0 7 -1 5 6
0 1

예제 출력 3

-1

알고리즘 분류

• 그래프 탐색
• 백트래킹

풀이

1부터 6까지의 좌표를 저장하고 6가지의 좌표를 방문하는 순서를 모두 탐색한다. 좌표가 6개이므로 경우의 수는 6!가지이다.

경우를 탐색하면서 각각의 경우마다 BFS를 최대 6번 수행한다. BFS를 수행하면서 뛰어갈 수 있는데, 이 때 벽에 부딪히거나 -1과 부딪히면 멈추고, 또 7이 적혀있는 칸으로 오면 멈춘다. 뛰어가는 동작 역시 한 번의 이동으로 간주한다.

BFS를 총 6번 수행했다면 1부터 6까지의 숫자가 적힌 칸을 전부 방문했다는 뜻이며, 이 때 걸리는 최소 시간을 구한다.

1부터 6까지 전부 방문하는 경우가 없다면 -1을 출력한다.

코드

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

using namespace std;
int R, C;
vector<pair<int, int> > Vec;
int MAP[MAX][MAX];
bool visited[MAX][MAX];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };
int Answer = INF;

void init() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            visited[i][j] = false;
        }
    }
}

void input() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            cin >> MAP[i][j];
            if ((MAP[i][j] >= 1) && (MAP[i][j] <= 6)) {
                Vec.push_back(make_pair(i, j));
            }
        }
    }
    cin >> R >> C;
}

int BFS(int Y, int X, int EndY, int EndX) {
    visited[Y][X] = true;
    queue<pair<pair<int, int>, int> > Q;
    Q.push(make_pair(make_pair(Y, X), 0));

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

        if ((NowY == EndY) && (NowX == EndX)) {
            return NowD;
        }

        for (int i = 0; i < 4; i++) {
            int NextY = NowY;
            int NextX = NowX;
            // 뛰어가는 경우
            while (1) {
                NextY += MoveY[i];
                NextX += MoveX[i];
                if ((NextY >= 0) && (NextY < 5) && (NextX >= 0) && (NextX < 5)) {
                    if (MAP[NextY][NextX] == 7) {
                        if (!visited[NextY][NextX]) {
                            visited[NextY][NextX] = true;
                            Q.push(make_pair(make_pair(NextY, NextX), NowD + 1));
                            break;
                        }
                        else {
                            break;
                        }
                    }
                    else if (MAP[NextY][NextX] == -1) {
                        NextY -= MoveY[i];
                        NextX -= MoveX[i];
                        if (!visited[NextY][NextX]) {
                            visited[NextY][NextX] = true;
                            Q.push(make_pair(make_pair(NextY, NextX), NowD + 1));
                            break;
                        }
                        else {
                            break;
                        }
                    }
                }
                else {
                    NextY -= MoveY[i];
                    NextX -= MoveX[i];
                        if (!visited[NextY][NextX]) {
                            visited[NextY][NextX] = true;
                            Q.push(make_pair(make_pair(NextY, NextX), NowD + 1));
                            break;
                        }
                        else {
                            break;
                        }
                }
            };
            // 결어가는 경우
            NextY = NowY + MoveY[i];
            NextX = NowX + MoveX[i];
            if ((NextY >= 0) && (NextY < 5) && (NextX >= 0) && (NextX < 5)) {
                if (MAP[NextY][NextX] != -1) {
                    if (!visited[NextY][NextX]) {
                        visited[NextY][NextX] = true;
                        Q.push(make_pair(make_pair(NextY, NextX), NowD + 1));
                    }
                }
            }
        }
    };

    return -1;
}

void settings() {
    sort(Vec.begin(), Vec.end());
    do {
        int Total = 0;
        pair<int, int> Start = make_pair(R, C);
        for (int i = 0; i < Vec.size(); i++) {
            init();
            int Time = BFS(Start.first, Start.second, Vec[i].first, Vec[i].second);
            if (Time == -1) {
                Total = -1;
                break;
            }
            else {
                Total += Time;
                Start = Vec[i];
            }
        }
        if (Total != -1) {
            Answer = min(Answer, Total);
        }
    } while (next_permutation(Vec.begin(), Vec.end()));
}

void find_Answer() {
    if (Answer == INF) {
        cout << "-1\n";
    }
    else {
        cout << Answer << "\n";
    }
}

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

    return 0;
}