🎲문제

---

주소 : 백준 3043

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

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

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

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

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

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

⌨ 입력

---

첫째 줄에 탱크의 수 N이 주어진다. (5 ≤ N ≤ 500)

다음 N개 줄에는 각 탱크가 있는 행의 번호 R과 열의 번호 C가 주어진다. (1 ≤ R, C ≤ N) 행과 열은 1부터 N까지 번호가 매겨져 있으며, 위에서 아래, 왼쪽에서 오른쪽 순서이다. 두 탱크가 같은 칸에 있는 경우는 없다.

✅ 풀이

---

풀이방법

그리디 알고리즘 문제이다. 여러 케이스들을 시뮬레이션 해봤을 때 각각의 행과 열에 하나씩 탱크가 올 수 있는지 특정 규칙이 있다. 최적의 경우 탱크들이 길을 막아 돌아가는 경우는 없으므로 돌아가지 않고 탱크들을 정렬하는 방법을 찾는 것이 핵심이다.

각각의 행과 열을 기준으로 탱크들을 정렬 후 아래로 내려가는 탱크 위로 올라가는 탱크 오른쪽으로 움직이는 탱크 왼쪽으로 움직이는 탱크를 배열(ArrayList)에 넣고 탱크들이 길을 막지 않고 움직일 수 있도록 순서대로 정렬하여 결과 배열(resultArray) 에 삽입한다.

1. 탱크들의 좌표를 입력받고 해당 탱크들을 x좌표 기준으로 오름 차순으로 정렬한다.

class Main{

    static Scanner sc = new Scanner(System.in);
    static Tank[] tankList = new Tank[501];
    static ArrayList<Tank> result = new ArrayList<>();

    static int N;

    public static void main(String[] args) throws Exception {
        N = sc.nextInt();

        for(int i = 0; i < N; i++)
            tankList[i] = new Tank(i,sc.nextInt()-1,sc.nextInt()-1);

        //상하이동
        Arrays.sort(tankList,0, N,(x, y) -> x.x - y.x);

1. 위로 가야하는 탱크와 아래로 가야하는 탱크의 배열을 만든다.
2. 만약 x = 0일때, 오름차순 정렬한 0번째 탱크가 x보다 아래에 있으면 해당 인덱스를 위로 가야하는 탱크 배열에 넣고, 위에 있을경우 아래로 가야하는 탱크 배열에 넣는다.
3. 이때 중요한것은 down탱크의 경우 인덱스 순서대로 탱크가 움직인다면 탱크끼리 충돌이 난다. 그러므로 제일 아래에 있는 탱크부터 움직이도록 배열을 뒤집어준다.

        ArrayList<Integer> upTank = new ArrayList<>(),downTank = new ArrayList<>();

        for(int i = 0; i < N; i++){
            if(tankList[i].x > i)
                upTank.add(i);
            if(tankList[i].x < i)
                downTank.add(i);
        }
        Collections.reverse(downTank);

1. upTank에 들어간 순서대로 결과 배열에 해당 탱크가 얼마나 올라가야하는지 계산해서 결과 배열에 넣는다. 이때, 위 아래 오른쪽 왼쪽 순서를 구분하지 않아도 되는 이유는 이미 위에서 충돌 날 만한 상황을 전부 순서대로 처리해 놨기 때문에 그대로 결과 배열에 넣기만 하면 된다.

for(int i : upTank){
            for(int j = i; j < tankList[i].x; j++)
                result.add(new Tank('U', tankList[i]));
}

for(int i : downTank){
    for(int j = tankList[i].x; j < i; j++)
        result.add(new Tank('D', tankList[i]));
}

1. 좌우이동하는 경우도 상하로 이동하는 경우와 같다. y좌표대로 정렬하고 각 인덱스와 좌표를 비교하여 좌우로 나누고 결과배열에 넣는다.

  Arrays.sort(tankList,0, N,(x, y) -> x.y - y.y);

        ArrayList<Integer> leftTank = new ArrayList<>(),rightTank = new ArrayList<>();

        for(int i = 0; i < N; i++){
            if(tankList[i].y > i)
                leftTank.add(i);
            if(tankList[i].y < i)
                rightTank.add(i);
        }

				Collections.reverse(rightTank);

        for(int i : leftTank){
            for(int j = i; j < tankList[i].y; j++)
                result.add(new Tank('L', tankList[i]));
        }

        for(int i : rightTank){
            for(int j = tankList[i].y; j < i; j++)
                result.add(new Tank('R', tankList[i]));
        }

전체 코드

---

import java.util.*;
import java.io.*;

class Main{

    static Scanner sc = new Scanner(System.in);
    static Tank[] tankList = new Tank[501];
    static ArrayList<Tank> result = new ArrayList<>();

    static int N;

    public static void main(String[] args) throws Exception {
        N = sc.nextInt();

        for(int i = 0; i < N; i++)
            tankList[i] = new Tank(i,sc.nextInt()-1,sc.nextInt()-1);

        //상하이동
        Arrays.sort(tankList,0, N,(x, y) -> x.x - y.x);

        ArrayList<Integer> upTank = new ArrayList<>(),downTank = new ArrayList<>();

        for(int i = 0; i < N; i++){
            if(tankList[i].x > i)
                upTank.add(i);
            if(tankList[i].x < i)
                downTank.add(i);
        }
        Collections.reverse(downTank);

        for(int i : upTank){
            for(int j = i; j < tankList[i].x; j++)
                result.add(new Tank('U', tankList[i]));
        }

        for(int i : downTank){
            for(int j = tankList[i].x; j < i; j++)
                result.add(new Tank('D', tankList[i]));
        }

        //좌우이동

        Arrays.sort(tankList,0, N,(x, y) -> x.y - y.y);

        ArrayList<Integer> leftTank = new ArrayList<>(),rightTank = new ArrayList<>();

        for(int i = 0; i < N; i++){
            if(tankList[i].y > i)
                leftTank.add(i);
            if(tankList[i].y < i)
                rightTank.add(i);
        }

				Collections.reverse(rightTank);

        for(int i : leftTank){
            for(int j = i; j < tankList[i].y; j++)
                result.add(new Tank('L', tankList[i]));
        }

        for(int i : rightTank){
            for(int j = tankList[i].y; j < i; j++)
                result.add(new Tank('R', tankList[i]));
        }

        System.out.println(result.size());

        for(Tank t : result)
            System.out.println((t.num+1) + " " + t.direction);
    }
}

class Tank{
    char direction;
    int num, x, y;

    public Tank(int num, int x, int y) {
        direction = 'N';
        this.num = num;
        this.x = x;
        this.y = y;
    }

    public Tank(char direction, Tank tank) {
        this.direction = direction;
        this.num = tank.num;
        this.x = tank.x;
        this.y = tank.y;
    }
}