[자바] 백준 14204 - 표 정렬 (java)

목차

문제 : boj14204

 

 

필요 알고리즘

• 그리디, 애드 혹
  
  • 일반적인 풀이 유형이 없는 애드 혹 문제이다. 내 경우엔 그리디한 방식으로 풀었다.

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

 

 

풀이

  참고로 '행 우선 순서' 라는 말은 아래처럼 행으로 쭉 정렬되어있음을 뜻한다.

1	2	3
4	5	6

 

  '열 우선 순서' 라면 아래와 같은 형태다.

1	3	5
2	4	6

 

  처음엔 원래 있어야 할 위치 기준 맨허튼 거리를 공책에 써보니 나름 의미 있어 보여서 그걸 기준으로 풀어보려고 했다. 근데 자꾸 틀려서 뭘 잘못했지 생각하던 중에, 어차피 행과 열 변경 순서는 결과에 영향을 끼치지 않으니, 그냥 그리디하게 무조건 있어야 할 위치에 무조건 보내면 되지 않을까? 라는 아이디어가 떠올랐다. 그래서 다 지우고 새로 짜니 싱겁게 통과되었다. 풀고보니 처음 시도하던 방식도 의미가 있는 방식이었는데, 수학적인 직관이 생각보다 많이 필요해 보였다. 난 수학적으로 푼 코드를 봐도 이게 왜 그런지 이해가 안됬다 ㅠ

 

  아무튼 풀이를 써보면.. 우선 예제 입력 5를 가지고 얘기해보자. 3x5 크기 이므로, 확실한 점은 무조건 열에 순서대로 1,2,3,4,5가 있어야 한다는 점이다. 따라서 무지성으로 각 열에서 순서대로 1,2,3,4,5이 포함된 열을 찾아서 있어야만 하는 위치로 열 통채로 옮겨준다. 이 과정에서 모순이 있을 경우 (1 찾고, 2 찾았는데 3이 1과 같은 열에 있거나 등) 바로 0을 출력하고 종료하면 된다.

 

  그리고 크기가 3x5로 고정되어 있으므로, 행 기준으로 맨 처음에 와야 하는 숫자도 정해져있다. 1, 6, 11이다. 코드에서는 'i*c+1' 이 수식이 저걸 구하는 부분이다. 따라서 1,6,11 순서대로 맨 처음으로 오도록 역시 무지성으로 행 통채로 바꿔준다. 역시 이 경우에 모순이 있을 경우 바로 0을 출력하고 종료하면 된다.

 

  즉, 열을 기준으로 1,2,3,4,5 처럼 무조건 있어야 하는 위치로 바꿨고, 행을 기준으로 1,6,11 처럼 무조건 있어야 하는 위치로 바꿨다(그리디). 그럼 이제 아무런 동작이 없어도 '행 우선 순서'로 맞춰져 있어야 하며, 만약 아래의 이미지처럼 어긋나 있는 부분이 있는 경우 저걸 정상적으로 맞출 수 있는 방법은 없다. 따라서 하나라도 어긋나면 0, 행 우선 순서가 맞다면 1을 출력해주면 된다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

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

    int r, c;
    int[][] arr;

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        arr = new int[r][c];
        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < c; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int j = 0; j < c; j++) {
            int columnIdx = columnInclude(j+1);
            if (columnIdx < j) {
                System.out.println(0);
                return;
            }

            swapColumn(j, columnIdx);
        }

        Set<Integer> exist = new HashSet<>();
        for (int i = 0; i < r; i++) {
            int rowIdx = rowInclude(i*c+1);
            if (rowIdx < i) {
                System.out.println(0);
                return;
            }

            swapRow(i, rowIdx);
        }

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (arr[i][j] != i*c+j+1) {
                    System.out.println(0);
                    return;
                }
            }
        }

        System.out.println(1);
    }

    private void swapColumn(final int j, final int includeIdx) {
        for (int i = 0; i < r; i++) {
            int tmp = arr[i][j];
            arr[i][j] = arr[i][includeIdx];
            arr[i][includeIdx] = tmp;
        }
    }

    private void swapRow(final int i, final int includeIdx) {
        for (int j = 0; j < c; j++) {
            int tmp = arr[i][j];
            arr[i][j] = arr[includeIdx][j];
            arr[includeIdx][j] = tmp;
        }
    }

    private int columnInclude(final int find) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (arr[i][j] == find) return j;
            }
        }
        return -1;
    }

    private int rowInclude(final int find) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (arr[i][j] == find) return i;
            }
        }
        return -1;
    }
}