[자바] 백준 3043 - 장난감 탱크 (java)

 문제 : boj3043

---

 

필요 알고리즘 개념

• 그리디 알고리즘
  
  • 논리적으로 최선의 경우를 만드는 과정을 잘 생각해 규칙을 정하면 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  솔직히 그리디쪽은 티어가 좀 애매한것 같다. 일단 풀이 생각하는 과정은 개인적으로 실버4인 25379번(피하자) 보다 쉬웠다. 다만 구현은 확실히 이 문제가 더 어렵긴 하다. 그렇다고 플래 받을 정도는 아닌 것 같아서 좀 애매한 것 같다.

 

  아무튼 내 풀이 생각과정은 다음과 같았다.

 

1. 문제에서 원하는건 '각 행과 열에 있는 탱크가 하나가' 되는 것이다. 그리고 NxN 크기의 맵이고, N개의 탱크가 있으므로 단순히 각 행마다 탱크가 하나씩 있고, 각 열마다 탱크가 하나씩 있으면 된다. 예를들어 N이 5일 경우의 가능한 몇 가지 경우는 아래와 같다.

 

 

2. 이 문제에서 어려움을 느낄만한 부분은, 각 탱크가 어떤식으로 움직여서 어떤 위치에 갈지까지 모두 정해줘야 한다는 점이다. 근데 잘 생각해보면 그리 어렵지 않다. 각 행에 각각 하나씩 있는 것과, 각 열에 각각 하나씩 있는건 서로 영향을 끼치지 않는다. 즉, 1~5번까지의 탱크에 대해, 1번 탱크가 첫번째 행에 갔다고 해서 1번 탱크가 존재할 수 있는 열의 범위가 결정되는데 영향을 끼치지 않는다. 즉, 각 탱크의 처음 위치 r과 c는 최종 결과를 생각할 때 서로 독립적이다.

 

  그렇다면 2차원이 아니라 1차원으로 생각해봐도 동일하다는건데, 맞다. 우선 r 값만 가지고 1차원 배열 N칸에 놓는다고 생각해보자. 이 경우 가장 최선으로 배치할 수 있는 방법은 처음 입력으로 들어온걸 정렬한 후 순서대로 N칸에 놓는 방식이다. 예를들어 r값만 봤을 때 1번부터 5번 탱크까지 '3, 3, 3, 4, 4' 라고 해보자. 이미 정렬된 데이터이므로 순서대로 1번 탱크는 r=3에서 r=1로 이동, 2번 탱크는 r=3에서 r=2로 이동, 3번 탱크는 r=3에서 그대로, 4번 탱크는 r=4에서 그대로, 5번 탱크는 r=4에서 r=5로 이동하면 된다.

 

  그럼 이걸 2차원에 어떻게 적용할까? 서로 독립적이라고 했으므로, 그냥 r값 기준으로 우선 정렬해서 r값 기준으로 1~N까지 위치를 잡고, 다시 c값 기준으로 정렬한 후 c값 기준으로 1~N까지 위치를 잡으면 된다!

 

 

3. '2'까지만 생각하고 제출해보면 틀리게 된다. 그 이유는 '두 탱크가 같은 칸에 있는 경우는 없다.' 라는 조건 때문이다. 난 배치가 끝난 후에 두 탱크가 같은 칸에 있으면 안된다고 판단하고 '2'까지만 생각했는데, 이동 중간에도 그런 경우가 없어야 했다. 이건 생각보다 간단하다.

 

  마찬가지로 1차원으로 생각해보면 된다. 1번탱크부터 5번탱크까지 r값이 '3, 3, 3, 3, 3' 이라고 해보자. 이 경우 1번탱크부터 순서대로 배치한다면, 1번탱크는 3->1, 2번탱크는 3->2, 3번탱크는 3 그대로, 4번 탱크는 3->4, 5번 탱크는 3->5... 로 가야하는데 5번 탱크의 경우 이미 4번탱크가 4번에 있으므로 겹치게 된다. 그럼 어떻게 해야할까? 처음 입력으로 들어온 r값을 기준으로 자기보다 작은 r값으로 이동하는 경우(위의 경우 1~2번 탱크는 자신보다 낮은 번호로 이동한다.)는 1번탱크부터 5번탱크까지 오름차순으로 처리하고, 자신보다 높은 r값으로 이동해야하는 녀석들(위의 경우 4번과 5번 탱크에 해당한다)은 5번탱크부터 1번탱크까지 내림차순 순서대로 처리하면 된다.

 

  즉, 우선 자신보다 낮은 위치로 갈 탱크들을 오름차순으로 처리한다. 1번탱크 3->1, 2번탱크 3->2. 그리고 자신보다 높은 위치로 가야할 녀석들을 내림차순을 처리한다. 5번탱크 3->5, 4번탱크 3->4. 이렇게 되면 5번탱크가 3->5로 이동한 후 4번탱크가 3->4로 이동하게 될 것이므로 겹치지 않게 된다. 이걸 구현하기가 까다롭게 느껴질 수 있는데, 코드로 보면 사실 케이스를 나눠서 생각할 필요는 없고 그냥 전부다 오름차순으로 한번 처리하고, 내림차순으로도 한번씩 처리해주면 된다. 처리 결과를 기존 탱크에 반영한다면 중복 처리될 일 없으므로 별 문제 없다. 주석을 참고해보자.

// vertical
Arrays.sort(arr, new Comparator<Tank>() {	// r값을 기준으로 정렬한다.
    @Override
    public int compare(Tank o1, Tank o2) {
        return o1.r - o2.r;
    }
});

for (int i = 0; i < n; i++) {	// 이게 오름차순으로 자신보다 낮은 위치로 가야하는 경우를 체크하는 코드이다.
    Tank cur = arr[i];
    int r = cur.r;	// 현재 보고있는 탱크의 r값
    int target = i+1;	// 해당 탱크가 이동해야 할 위치
    while (r>target) {	// 현재 탱크의 r값이 이동해야할 위치보다 큰 동안 r을 감소시키면서 이동한다.
        cnt++;
        answer.append(cur.num).append(' ').append(MOVE_UP).append('\n');
        r--;
    }
    cur.r = r;	// 오름차순으로 처리한 녀석들은 여기서 r값을 갱신하므로 이하 내림차순으로 갈 때 중복 처리되지 않게된다.
}

for (int i = n-1; i >= 0; i--) { // 이게 내림차순으로 자신보다 낮은 위치로 가야하는 경우를 체크하는 코드이다.
    Tank cur = arr[i];
    int r = cur.r;
    int target = i+1;
    while (r<target) {
        cnt++;
        answer.append(cur.num).append(' ').append(MOVE_DOWN).append('\n');
        r++;
    }
    cur.r = r;
}

 

  그럼 위에서 설명한게 2차원으로 이동해도 동일하게 적용될까? 2차원으로 가게되면, 예를들어서 탱크가 (2,1)과 (3,1)일 경우 (2,1)인 녀석이 더 큰 r값으로 움직이면 겹칠테지만, (2,1)과 (3,4)인 녀석이 있었다면 사실 (2,1)인 녀석은 r값을 아무리 변경해도 영향을 끼치지 않으니 1차원적으로 r값만 생각한걸로는 부족하다고 느낄 수 있다.

 

  하지만 1차원으로 생각해 작성한 위의 내용은 사실 최악의 경우를 본 것이라 봐도 된다. 즉, 위에선 r값만 가지고 생각했는데 그건 모든 c값이 동일한 경우와 같다(1차원이었으니깐). c값이 모두 동일해도 겹치지 않음을 보였으므로, (2,1)과 (3,1)이던, (2,1)과 (3,4)였던 상관이 없다. 그러니 신경쓰지 않고 위 방식대로만 구현하면 된다.

 

  최종 코드는 위에서 본 코드에 추가로, '2'의 마지막 문단에서 얘기한 방식대로 c값을 기준으로 정렬한 후 위의 코드를 동일하게 진행하는게 추가되었다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

class Tank {
    int r, c, num;
    static int n = 1;
    public Tank(int r, int c) {
        this.r = r;
        this.c = c;
        this.num = n++;
    }
}

public class Main {
    private static final Character MOVE_DOWN    = 'D';
    private static final Character MOVE_UP      = 'U';
    private static final Character MOVE_LEFT    = 'L';
    private static final Character MOVE_RIGHT   = 'R';

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Tank[] arr = new Tank[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i] = new Tank(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        StringBuilder answer = new StringBuilder();
        int cnt = 0;

        // vertical
        Arrays.sort(arr, new Comparator<Tank>() {
            @Override
            public int compare(Tank o1, Tank o2) {
                return o1.r - o2.r;
            }
        });
        for (int i = 0; i < n; i++) {
            Tank cur = arr[i];
            int r = cur.r;
            int target = i+1;
            while (r>target) {
                cnt++;
                answer.append(cur.num).append(' ').append(MOVE_UP).append('\n');
                r--;
            }
            cur.r = r;
        }
        for (int i = n-1; i >= 0; i--) {
            Tank cur = arr[i];
            int r = cur.r;
            int target = i+1;
            while (r<target) {
                cnt++;
                answer.append(cur.num).append(' ').append(MOVE_DOWN).append('\n');
                r++;
            }
            cur.r = r;
        }

        // horizontal
        Arrays.sort(arr, new Comparator<Tank>() {
            @Override
            public int compare(Tank o1, Tank o2) {
                return o1.c - o2.c;
            }
        });
        for (int i = 0; i < n; i++) {
            Tank cur = arr[i];
            int c = cur.c;
            int target = i+1;
            while (c>target) {
                cnt++;
                answer.append(cur.num).append(' ').append(MOVE_LEFT).append('\n');
                c--;
            }
        }
        for (int i = n-1; i >= 0; i--) {
            Tank cur = arr[i];
            int c = cur.c;
            int target = i+1;
            while (c<target) {
                cnt++;
                answer.append(cur.num).append(' ').append(MOVE_RIGHT).append('\n');
                c++;
            }
        }

        // print answer
        System.out.println(cnt);
        System.out.print(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}