백준 3043 - 장난감 탱크

 

 

문제 설명

상근이는 생일 선물로 장난감 탱크 N개를 받았다. 탱크를 가지고 놀기 전장을 만들었다. 전장은 나무판 위에 N행 N열 크기로 만들었다.

각 탱크가 한 번에 움직일 수 칸은 인접한 네 칸이다. 탱크는 같은 행과 열에 있는 모든 칸을 공격할 수 있다. 따라서, 탱크는 자신이 있는 칸에 해당하는 행과 열을 보호하고 있다고 말할 수 있다.

두 탱크가 동시에 같은 정사각형 안에 있을 수는 없다.

이렇게 탱크를 가지고 두~세시간 동안 열심히 놀고 있었다. 상근이의 어머니는 점심까지 거르면서 놀고있는 상근이를 못마땅하게 생각했고, 당장 점심을 먹으러 오라고 소리쳤다. 상근이는 탱크가 모든 행과 열을 보호하게 배치를 바꾼 다음에 점심을 먹으러 가려고 한다. (즉, 각각의 행과 열에 하나의 탱크만 있어야 한다)

이렇게 배치를 바꾸는 경우에 탱크를 움직이는 횟수를 적게 하려고 한다.

탱크를 몇 번 움직이면, 각 행과 열에 있는 탱크가 하나가 되는지 구하는 프로그램을 작성하시오. 움직이는 방법이 여러 가지라면 탱크를 움직이는 횟수가 가장 작은 것을 찾는다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 탱크를 N x N 행렬에 가로, 세로가 겹치지 않도록 배치하려 할 때 최소 이동 횟수와 연산을 트래킹 하는 것이다.

N-Queen과 비슷한 문제라고 생각하면 된다.

 

N-Queen 같은 경우에는 백트래킹이나 행과 열을 합쳐서 문제를 축약하는 등의 방법으로 구현하지만 해당 문제는 그리디를 이용하여 풀 수 있다.

 

우선, 문제를 간단하게 바꿔보자.

모든 지역을 커버할 수 있다는 얘기는 가로, 세로가 겹치지 않도록 배치해야 된다는 뜻이다.

즉, 현재 상태에서 같은 행 혹은 같은 열에 존재하는 탱크들을 적절히 이동시켜 하나도 겹치지 않도록 배치하면 된다.

이때, 최소한으로 탱크를 이동시키기 위해서는 올바른 위치에 있는 탱크는 이동시키지 않는 것이 유리하게 보인다.

예를 들어, 같은 행에 3개의 탱크가 존재한다면 2개만 이동시키면 된다는 뜻이다.

하지만, 그러지 않아도 상관없다.

두 경우 모두 4로 이동한 거리의 총합은 같다.

즉, 모든 행, 어떠한 탱크를 움직여도 상관없다는 뜻이 된다.

 

하지만, 첫 번째 경우에는 문제가 하나 있다.

4번 탱크가 2번 탱크를 지나가야 된다.

그렇다면 이동 중 2, 4번 탱크가 하나의 칸에 위치하게 되어 문제의 조건에 맞지 않는 방법이 된다.

 

정리하면, 최적의 배치를 위해 어떤 탱크든 조작해도 되지만 겹쳐서 이동하지 않게 하기 위해 이동하려는 방향에 가까운 탱크부터 옮겨야 한다.

따라서, 초기 상태를 입력받아 정렬한다면 i번째 칸에 위치해야 하는 탱크를 알 수 있다.

모든 탱크는 1~N까지 행, 열에 위치해야 하기 때문에 i번째 칸보다 오른쪽에 존재한다면 왼쪽으로 이동시켜야 하며 반대의 경우에는 오른쪽으로 이동시키면 된다.

이를 상, 하, 좌, 우 총 4개의 방향에 대해 계산한 뒤 이동시키면 된다.

 

예를 들어 보자.

초기 상태는 다음과 같다.

오른쪽에는 행을 기준으로 정렬한 결과를 나타낸다.

정렬한 기준이 의미하는 것은 1번 탱크는 1번째 행에 존재해야 한다는 것이다.

마찬가지로 2번 탱크는 2번째 행에 존재해야 한다.

즉, 두 탱크는 각각 2번, 3번 행에 존재하기 때문에 위로 1칸씩 이동해야 한다.

3번 탱크는 3번째 행에 존재하기 때문에 이동할 필요가 없다. 

반대로 4번, 5번 탱크는 각각 4번, 5번째 행에 존재해야 한다.

하지만, 3번, 4번에 있기 때문에 1칸씩 아래로 이동해야 한다.

즉 다음과 같이 이동해야 한다. 

이때, 주의할 점은 이동하는 방향의 탱크를 지나쳐가면 안 되기 때문에 이동방향 쪽에 위치한 탱크부터 우선적으로 이동시켜야 한다.

즉, 위로 이동할 때는 위에 위치한 1번 탱크부터 2번 탱크 순으로, 아래로 이동할 때는 아래에 위치한 5번 탱크부터 4번 탱크 순으로 이동시켜야 한다.

cin >> N;

//idx 조정
vector<Tank> rows(1);
vector<Tank> cols(1);

for (int i = 1; i <= N; i++)
{
    int a, b;
    cin >> a >> b;

    rows.push_back({ a, b, i });
    cols.push_back({ b, a, i });
}

//정렬
sort(rows.begin(), rows.end());
sort(cols.begin(), cols.end());

//이동할 탱크 저장
deque<int> up;
deque<int> down;
deque<int> left;
deque<int> right;
for (int i = 1; i <= N; i++)
{
    //i행보다 아래에 있다면 up, i행보다 위에 있다면 down
    if (rows[i].first > i) up.push_back(i);
    else if (rows[i].first < i) down.push_front(i);

    //i열보다 오른쪽에 있다면 left, i열보다 왼쪽에 있다면 right
    if (cols[i].first > i) left.push_back(i);
    else if (cols[i].first < i) right.push_front(i);
}

down과 right은 역순으로 저장하는 것에 유의해야 한다.

 

이동할 탱크를 모두 골라냈다.

이제 각 이동을 처리하면 된다.

    vector<pair<int, char>> moves;
    //move up
    for (int i = 0; i < up.size(); i++)
    {
        //y = 목표 row, rows[up[i]].first = 초기 row값
        for (int y = up[i]; y < rows[up[i]].first; y++)
        {
            moves.push_back({ rows[up[i]].idx, 'U' });
        }
    }

    //move down
    for (int i = 0; i < down.size(); i++)
    {
        for (int y = rows[down[i]].first; y < down[i]; y++)
        {
            moves.push_back({ rows[down[i]].idx, 'D' });
        }
    }

    //move left
    for (int i = 0; i < left.size(); i++)
    {
        for (int x = left[i]; x < cols[left[i]].first; x++)
        {
            moves.push_back({ cols[left[i]].idx, 'L' });
        }
    }

    //move right
    for (int i = 0; i < right.size(); i++)
    {
        for (int x = cols[right[i]].first; x < right[i]; x++)
        {
            moves.push_back({ cols[right[i]].idx, 'R' });
        }
    }

    cout << moves.size() << "\n";
    for (auto [idx, dir] : moves)
    {
        cout << idx << " " << dir << "\n";
    }

 

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

struct Tank
{
    Tank() = default;
    Tank(int a, int b, int i) : first(a), second(b), idx(i) {};
    int idx, first, second;

    bool operator < (const Tank& other)
    {
        if (first == other.first)
        {
            return second < other.second;
        }

        return first < other.first;
    }
};

int N;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(4);

    cin >> N;

    vector<Tank> rows(1);
    vector<Tank> cols(1);

    for (int i = 1; i <= N; i++)
    {
        int a, b;
        cin >> a >> b;

        rows.push_back({ a, b, i });
        cols.push_back({ b, a, i });
    }

    sort(rows.begin(), rows.end());
    sort(cols.begin(), cols.end());

    deque<int> up;
    deque<int> down;
    deque<int> left;
    deque<int> right;
    for (int i = 1; i <= N; i++)
    {
        if (rows[i].first > i) up.push_back(i);
        else if(rows[i].first < i) down.push_front(i);

        if (cols[i].first > i) left.push_back(i);
        else if (cols[i].first < i) right.push_front(i);
    }

    vector<pair<int, char>> moves;
    //move up
    for (int i = 0; i < up.size(); i++)
    {
        //y = 목표 row, rows[up[i]].first = 초기 row값
        for (int y = up[i]; y < rows[up[i]].first; y++)
        {
            moves.push_back({ rows[up[i]].idx, 'U' });
        }
    }

    //move down
    for (int i = 0; i < down.size(); i++)
    {
        for (int y = rows[down[i]].first; y < down[i]; y++)
        {
            moves.push_back({ rows[down[i]].idx, 'D' });
        }
    }

    //move left
    for (int i = 0; i < left.size(); i++)
    {
        for (int x = left[i]; x < cols[left[i]].first; x++)
        {
            moves.push_back({ cols[left[i]].idx, 'L' });
        }
    }

    //move right
    for (int i = 0; i < right.size(); i++)
    {
        for (int x = cols[right[i]].first; x < right[i]; x++)
        {
            moves.push_back({ cols[right[i]].idx, 'R' });
        }
    }

    cout << moves.size() << "\n";
    for (auto [idx, dir] : moves)
    {
        cout << idx << " " << dir << "\n";
    }

    return 0;
}

---