[BOJ] 10157 자리배정 - JAVA

1. 문제

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

10157번: 자리배정

C*R 공연장에 가장 왼쪽부터 시계방향으로 사람을 채운다. 좌표는 가장 왼쪽 아래가 (1,1)이다.

K번째 관객의 x, y좌표를 출력한다. 만약 좌석을 배정할 수 없는 경우는 0을 출력한다.

---

2. 풀이

1. 배정할 수 없는 경우(K>C*R)부터 제외한다.
2. 시작인덱스는 (0,R-1)이다. 위->오른쪽->아래->왼쪽으로 움직인다.
3. 다음 x,y를 구하고 범위에 벗어나거나 이미 저장된 번호가 있다면 방향을 바꾸고 현재 숫자를 -1한다.
   • 이때, 방향은 무한히 변경되어야 하므로 (d+1)%4를 한다.
   • 현재 숫자-1의 이유는 for반복문을 사용했기 때문이다.
4. 다음 x,y가 유효하다면 그 값을 저장한다.
5. num==K라면 반복을 끝내는데, 문제의 인덱스가 1부터 시작하고 y는 현재 인덱스의 정반대로 숫자를 매기므로 x+1, R-y를 출력한다.

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

public class BOJ_10157_자리배정 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());

        int C = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(in.readLine());

        if(K>C*R){
            System.out.println(0);
            return;
        }

        int[][] deltas = {{-1,0},{0,1},{1,0},{0,-1}}; //위, 오른쪽, 아래, 왼쪽
        int[][] hall = new int[R][C];
        
        //시작인덱스, 시작방향
        int x = 0, y = R-1;
        int d=0;
        
        for(int num=1;num<=C*R;num++){
            hall[y][x] = num;

            if(num==K){
                System.out.println((x+1)+" "+(R-y));
                return;
            }

            int nx = x+deltas[d][1];
            int ny = y+deltas[d][0];

            if(nx<0 || nx>=C || ny<0 || ny>=R || hall[ny][nx]!=0) {
                d = (d+1)%4;
                --num;
                continue;
            }

            x = nx;
            y = ny;
        }
    }
}

---

3. 결과