[BOJ] 10157 자리배정(Java)

문제

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

10157번: 자리배정

풀이

- 사각형의 가장 바깥 쪽 테두리부터 가장 안쪽 테두리까지 탐색하며 k가 속한 테두리를 찾는다.

    - r X c 사각형일 때 시작 위치 (x,y)에서의 대기번호가 1이라면 같은 테두리의 마지막 대기번호는 r*2 + c*2 - 4가 된다.

    - 마지막 대기번호보다 k가 크면 x,y는 1씩 증가, r, c는 2씩 감소, 다음 대기번호는 마지막 대기번호+1이 된다.

- k가 속한 테두리를 찾으면 x,y부터 시계방향으로 탐색하며 k를 찾는다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    private static final int[][] DELTAS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    private static int r;
    private static int c;
    private static int k;
    private static int waitingNumber;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        c = Integer.parseInt(stringTokenizer.nextToken());
        r = Integer.parseInt(stringTokenizer.nextToken());
        k = Integer.parseInt(bufferedReader.readLine());

        if (k > r * c) {
            System.out.println(0);
            return;
        }

        waitingNumber = 1;
        int x = 1;
        int y = 1;
        int edge = r * 2 + c * 2 - 4;
        while (edge < k) {
            r -= 2;
            c -= 2;
            x++;
            y++;
            waitingNumber = edge+1;
            edge += r * 2 + c * 2 - 4;
        }

        for (int i = 0, deltasLength = DELTAS.length; i < deltasLength; i++) {
            int[] delta = DELTAS[i];
            int dx = x + delta[0];
            int dy = y + delta[1];
            while (canGo(i, dx, x, dy, y)) {
                dx += delta[0];
                dy += delta[1];
            }
            x = dx - delta[0];
            y = dy - delta[1];
            if (waitingNumber - 1 == k) {
                break;
            }
        }
        System.out.println(x + " " + y);
    }

    private static boolean canGo(int direction, int dx, int x, int dy, int y) {
        if (direction < 2) {
            return dx >= x && dx < x + c && dy >= y && dy < y + r && waitingNumber++ != k;
        } else {
            return dx <= x && dx > x - c && dy <= y && dy > y - r && waitingNumber++ != k;
        }
    }
}