[백준 Baekjoon] 10157번 자리배정 - JAVA

백준 Baekjoon 10157번 자리배정 - JAVA

---

문제 풀이

대기 순서가 K인 관객에게 배정될 좌석 번호(x,y)를 찾는 문제이다. 문제 설명에서 주어졌듯이 배열을 달팽이 모형으로 순회하며 K번째가 될때 위치를 출력해주면 된다. 배열을 달팽이 모형으로 순회할줄만 알면 어렵지 않은 문제이다.

초기 위치를 x = R - 1, y = 0으로 방향은 위, 오른쪽, 아래, 왼쪽 순으로 초기화 하였다.
while문에서 k번째가 될때까지 횟수 cnt를 증가 시키며 k가 될때에 종료된다.
다음으로 배정될 좌석을 찾고 지도 밖으로 벗어나거나 이미 배정된 자리인 경우 방향을 돌려 배정하도록 하였다.
- 처음 한바퀴를 돌 때에는 0보다 작거나 R, C보다 크면 지도 밖을 벗어난다.
- 그다음 바퀴부터는 이미 배정된 좌석인지 확인하며 방향을 돌리면 된다.

소스 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int C = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        int K = Integer.parseInt(br.readLine());

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

        int dx[] = {-1, 0, 1, 0};
        int dy[] = {0, 1, 0, -1};

        boolean[][] visit = new boolean[R][C];

        int cnt = 0, x = R - 1, y = 0, dir = 0;
        while (++cnt != K) {
            visit[x][y] = true;
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx < 0 || ny < 0 || nx >= R || ny >= C || visit[nx][ny]) {
                dir = ++dir % 4;
                nx = x + dx[dir];
                ny = y + dy[dir];
            }

            x = nx;
            y = ny;
        }

        System.out.println((y + 1) + " " + (R - x));
    }
}