백준 3043번 장난감 탱크

문제 링크입니다: https://www.acmicpc.net/problem/3043

문제에서 요구하는 조건은 각각의 행과 열에 오직 하나의 탱크를 배치하는 것입니다.

따라서, 탱크를 상하로 먼저 움직인 뒤 좌우로 움직여주면 조건을 충족시킬 수 있습니다.

탱크를 움직이는 기준은 아래와 같습니다.

1. 상하로 움직일 경우 y를 기준으로 정렬한 뒤 1 ~ N까지 반복문을 돌리면서 y가 해당 칸보다 아래에 있으면 위로 가야하고 해당 칸보다 위에 있으면 아래로 움직여줘야합니다.

2. 좌우로 움직일 경우도 마찬가지로 x를 기준으로 정렬한 뒤 1~N까지 반복문을 돌리면서 x가 해당 칸보다 오른쪽에 있으면 왼쪽으로 가야하고 왼쪽에 있으면 오른쪽으로 움직여줘야합니다.

ssangba55(https://blog.naver.com/pasdfq/221253664523)님이 문제가 그리디 알고리즘으로 분류된 이유를 잘 설명해놓으셨기 때문에 설명을 추가합니다!

위로 가는 탱크는 아래로 가는 탱크보다 아래에 있을 수 없고, 마찬가지로 왼쪽으로 가는 탱크는 오른쪽으로 가는 탱크보다 오른쪽에 있을 수 없기 때문에 위로 가는 탱크와 왼쪽으로 가는 탱크는 처음부터, 아래로 가는 탱크와 오른쪽으로 가는 탱크는 끝에서부터 움직입니다!

따라서, 서로가 길을 막는 경우는 없습니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int N;

vector<pair<int, char>> result;

 

//정렬 기준

bool cmp(const pair<int, pair<int, int>> a, const pair<int, pair<int, int>> b)

{

        if (a.second.first < b.second.first)

                 return true;

        else if (a.second.first == b.second.first)

                 return a.second.second < b.second.second;

        else

                 return false;

}

 

void upDown(vector<pair<int, pair<int, int>>> &v)

{

        vector<int> up, down;

 

        //i 기준으로 위로 갈지 아래로 갈지 정함

        for (int i = 1; i <= N; i++)

        {

                 if (v[i - 1].second.first > i)

                         up.push_back(i);

                 if (v[i - 1].second.first < i)

                         down.push_back(i);

        }

 

        for (int i = 0; i < up.size(); i++)

                 for (int y = up[i]; y < v[up[i] - 1].second.first; y++)

                         result.push_back(make_pair(v[up[i] - 1].first, 'U'));

        //아래로 가는 탱크는 뒤에서부터 움직인다

        reverse(down.begin(), down.end());

        for (int i = 0; i < down.size(); i++)

                 for (int y = v[down[i] - 1].second.first; y < down[i]; y++)

                         result.push_back(make_pair(v[down[i] - 1].first, 'D'));

}

 

void leftRight(vector<pair<int, pair<int, int>>> &v)

{

        vector<int> left, right;

 

        //i 기준으로 왼쪽으로 갈지 오른쪽으로 갈지 정함

        for (int i = 1; i <= N; i++)

        {

                 if (v[i - 1].second.first > i)

                         left.push_back(i);

                 if (v[i - 1].second.first < i)

                         right.push_back(i);

        }

 

        for (int i = 0; i < left.size(); i++)

                 for (int x = left[i]; x < v[left[i] - 1].second.first; x++)

                         result.push_back(make_pair(v[left[i] - 1].first, 'L'));

        //오른쪽으로 가는 탱크는 끝에서부터 움직인다

        reverse(right.begin(), right.end());

        for (int i = 0; i < right.size(); i++)

                 for (int x = v[right[i] - 1].second.first; x < right[i]; x++)

                         result.push_back(make_pair(v[right[i] - 1].first, 'R'));

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상 위해

 

        cin >> N;

        vector < pair<int, pair<int, int>>> yFirst; //세로 기준

        vector < pair<int, pair<int, int>>> xFirst; //가로 기준

 

        for (int i = 1; i <= N; i++)

        {

                 int y, x;

                 cin >> y >> x;

 

                 yFirst.push_back(make_pair(i, make_pair(y, x)));

                 xFirst.push_back(make_pair(i, make_pair(x, y)));

        }

       

        sort(yFirst.begin(), yFirst.end(), cmp);

        upDown(yFirst);

        sort(xFirst.begin(), xFirst.end(), cmp);

        leftRight(xFirst);

       

        //endl 시간초과

        cout << result.size() << "\n";

        for (int i = 0; i < result.size(); i++)

                 cout << result[i].first << " " << result[i].second << "\n";

 

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~