[BOJ/Gold 5] 백준 25585 86 ─에이티식스─ 1(C++)

문제 링크

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

25585번: 86 ─에이티식스─ 1

 

 

문제

산마그놀리아 공화국은 '레기온'이라는 인공지능 무인 병기들과 전쟁 중이다. 공화국은 레기온에 대항할 수단으로 '저거노트'라는 보행 병기를 개발했다. 공화국 군인들은 이 저거노트에 탑승해서 레기온에 맞서 싸운다.

신에이 노우젠은 동부전선 제1전대의 전대장이자 근접전의 대가이다. 그는 레기온들의 위치를 전부 파악할 수 있는 이능력이 있다. 그의 전투 스타일은 직접 레기온이 있는 위치로 도약해서 빠르게 해치우는 것이다. 저거노트는 화력이 다소 약하지만, 기동성이 뛰어나다는 장점이 있기 때문이다.

저거노트는 대각선 네 방향으로 이동할 수 있다. 현재 좌표가 (r,c)라면 (r−1,c−1), (r−1,c+1), (r+1,c−1), (r+1,c+1)로 움직일 수 있다.

<저거노트 이동 가능 좌표>

저거노트가 한 번 이동하는 데는 1초 걸린다. 신에이 노우젠은 레기온이 있는 위치로 직접 이동해서 레기온을 해치우는데, 전투에 매우 뛰어나서 레기온이 있는 위치로 도약하기만 하면 바로 레기온을 해치울 수 있다. 즉, 레기온을 해치우는 데 걸리는 시간은 0이다.

기습받은 레기온들은 당황하여 모두 움직임을 멈춘 상태다. 레기온들의 위치가 주어졌을 때, 신에이 노우젠이 레기온을 모두 해치우는 게 가능한지 여부, 그리고 가능하다면 모두 해치우는데 걸리는 최소 시간을 계산해보자.

신에이 노우젠은 전장을 벗어나 이동할 수는 없다.

입력

첫 번째 줄에 전장의 크기 N이 주어진다. 전장은 N×N 크기 좌표로 이루어져 있다. 다음 N개의 줄에는 전장의 정보가 주어진다. 각 줄마다 N개의 좌표 정보가 주어지며 0은 빈칸, 1은 레기온, 2는 신에이 노우젠의 현재 위치를 나타낸다.

레기온 개수는 아무리 많아도 10개를 넘기지 않는다.

•  1 ≤ N ≤ 100
•  0 ≤ 레기온 개수 ≤ min(N^2−1, 10)
• 신에이 노우젠의 위치는 유일하다.

출력

전장에 레기온이 없거나 모든 레기온을 해치울 수 있다면 첫 줄에 "Undertaker" 를 출력하고 둘째 줄에 레기온을 모두 해치우는데 걸리는 최소 시간을 초 단위로 출력한다. 모든 레기온을 해치울 수 없다면 "Shorei" 를 출력한다.

예제 입력 1

5
0 2 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 0 0 0

예제 출력 1

Undertaker
3

예제 입력 2

5
0 2 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 0 0
0 0 1 0 0

예제 출력 2

Shorei

알고리즘 분류

• 백트래킹

풀이

우선 저거노트는 대각선으로만 이동할 수 있다. 그럴려면 BFS로 대각선으로 움직이면서 거리를 직접 재야 한다.

하지만 그렇게 하면 시간이 오래 걸린다. 따라서 현재 위치에서 다음 레기온의 위치 간 거리를 그냥 사칙연산으로 구해야 한다.

따라서 전장을 45도 각도로 돌리면 현재 위치와 다음 레기온 사이의 거리를 좀 더 수월하게 구할 수 있다.

레기온이 존재하지 않는다면 탐색할 필요는 없지만, 하나 이상 존재한다면 레기온들의 현재 위치에 대한 정보를 벡터로 관리한다.

그리고 next_permutation()을 활용하여 레기온을 탐색하는 경우의 수를 전부 따져가면서 레기온을 잡을 수 있는지, 전부 잡았을 때 걸리는 최소의 시간이 얼마인지를 구한다.

레기온은 아무리 많아도 10개체까지만 존재하기 때문에 모든 경우의 수를 다 따져봐도 360만개 정도이므로 시간 내에 연산을 처리할 수 있다.

레기온을 전부 잡을 수 있는 경우가 없다면 Shorei를 출력하고, 전부 잡을 수 있다면 Undertaker를 출력하고 다음 줄에 최소의 시간을 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 201
#define INF 2e9
#define FASTIO cin.tie(0); cout.tie(0);

using namespace std;
int N;
int MAP[MAX][MAX];
pair<int, int> Home;
vector<pair<int, int> > Enemy;
int Answer = INF;

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> MAP[i + j][N - 1 - i + j];
            if (MAP[i + j][N - 1 - i + j] == 1) {
                Enemy.push_back(make_pair(i + j, N - 1 - i + j));
            }
            else if (MAP[i + j][N - 1 - i + j] == 2) {
                Home = make_pair(i + j, N - 1 - i + j);
            }
        }
    }
}

void settings() {
    if (Enemy.empty()) {
        Answer = 0;
        return;
    }
    sort(Enemy.begin(), Enemy.end());
    do {
        int NowY = Home.first;
        int NowX = Home.second;
        bool Finish = true;
        int Time = 0;
        for (int i = 0; i < Enemy.size(); i++) {
            int SubY = abs(NowY - Enemy[i].first);
            int SubX = abs(NowX - Enemy[i].second);
            if ((SubY % 2 == 0) && (SubX % 2 == 0)) {
                Time += (SubY + SubX);
                NowY = Enemy[i].first;
                NowX = Enemy[i].second;
            }
            else {
                Finish = false;
                break;
            }
        }
        if (Finish) {
            Answer = min(Answer, Time / 2);
        }
    } while (next_permutation(Enemy.begin(), Enemy.end()));
}

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

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

    return 0;
}