[실전 문제] seat

1. 문제

어떤 공연장에는 가로로 R개, 세로로 C개의 좌석이 R×C격자형으로 배치되어 있다. 각 좌석의 번호는 해당 격자의 좌표 (x,y)로 표시된다.

예를 들어보자. 아래 그림은 가로 7개, 세로 6개 좌석으로 구성된 7×6격자형 좌석배치를 보여주고 있다. 그림에서 각 단위 사각형은 개별 좌석을 나타내며, 그 안에 표시된 값 (x,y)는 해당 좌석의 번호를 나타낸다. 가장 왼쪽 아래의 좌석번호는 (1,1)이며, 가장 오른쪽 위 좌석의 번호는 (7,6)이다.

이 공연장에 입장하기 위하여 많은 사람이 대기줄에 서있다. 기다리고 있는 사람들은 제일 앞에서부터 1, 2, 3, 4, . 순으로 대기번호표를 받았다. 우리는 대기번호를 가진 사람들에 대하여 (1,1)위치 좌석부터 시작하여 시계방향으로 돌아가면서 비어있는 좌석에 관객을 순서대로 배정한다. 이것을 좀 더 구체적으로 설명하면 다음과 같다.

 

먼저 첫 번째 사람, 즉 대기번호 1인 사람은 자리 (1,1)에 배정한다. 그 다음에는 위쪽 방향의 좌석으로 올라가면서 다음 사람들을 배정한다. 만일 더 이상 위쪽 방향으로 빈 좌석이 없으면 오른쪽으로 가면서 배정한다. 오른쪽에 더 이상 빈자리가 없으면 아래쪽으로 내려간다. 그리고 아래쪽에 더 이상 자리가 없으면 왼쪽으로 가면서 남은 빈 좌석을 배정한다. 이 후 왼쪽으로 더 이상의 빈 좌석이 없으면 다시 위쪽으로 배정하고, 이 과정을 모든 좌석이 배정될 때까지 반복한다.

 

아래 그림은 7×6공연장에서 대기번호 1번부터 42번까지의 관객이 좌석에 배정된 결과를 보여주고 있다.

여러분은 공연장의 크기를 나타내는 자연수 R과 C가 주어져 있을 때, 대기 순서가 K인 관객에게 배정될 좌석 번호 (x,y)를 찾는 프로그램을 작성해야 한다.

---

입력

첫 줄에는 공연장의 격자 크기를 나타내는 정수 R과 C가 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ R, C ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. 단 1 ≤ K ≤ 100,000,000이다.

출력

입력으로 제시된 대기번호 K인 관객에게 배정될 좌석번호 (x,y)를 구해서 두 값, x와 y를 하나의 공백을 사이에 두고 출력해야 한다. 만일 모든 좌석이 배정되어 해당 대기번호의 관객에게 좌석을 배정할 수 없는 경우에는 0(숫자 영)을 출력해야 한다.

예제 입력

7 6
12

예제 출력

7 6

 

 

 

2. 풀이

이 문제는 배열을 다루는데 있어서 까다로운 문제라고 생각한다. 우선, 주어진 문제의 예시를 보면, (0, 0)이 아닌 (1, 1)부터 시작하며, (1, 1)이 왼쪽 하단에 위치함을 볼 수 있다. 만약 왼쪽 하단부터 값을 채운다고 한다면 코드를 작성하는데 어려움을 느낄 수 있다.

 

하지만 위의 그림을 오른쪽 방향으로 90도로 돌리면, 쉽게 풀 수 있다. 회전시켰을 경우, 찾고자 하는 값의 위치도 변한다고 생각할 수 있지만, 실제로 그림을 회전을 시켜도, 위치는 변하지 않음을 알 수 있다. 또한 (1, 1)의 위치가 왼쪽 상단에 위치되므로, 기존에 배열을 탐색할 때의 형태로 갖춰지기 때문에, 코드 작성에 부담이 덜어진다.

그 다음으로 생각해야하는 부분은, 이동하는 방향이다. 문제에서 주어진것 처럼 시계방향으로 값을 채워넣기 때문에, 끝에 도달했을 때 어떤 방향으로 값을 채워야하는지에 대한 아이디어가 필요하다.

 

방향 변경의 아이디어로는, 배열의 테두리에 1로 모두 채우고 (1, 1) 부터 배열에 1의 값을 넣으면서 1을 만나게 되면 방향을 돌릴 수 있도록 하면 된다.

 

 

 

방향 변경에 대한 코드는, 현재 위치를 기준으로 상하좌우 중, 1이 있을 경우 방향을 변경하도록 하면 된다.

• direction = (direction + 1) % 4

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    // 상, 우, 하, 좌
    private static int[] dy = {-1, 0, 1, 0};
    private static int[] dx = {0, 1, 0, -1};
    private static int direction  = 0;

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken()); // 가로, 열, 5 이상
        int c = Integer.parseInt(st.nextToken()); // 세로, 행, 20 이하
        int k = Integer.parseInt(br.readLine()); // 1 이상, 100000000 이하

        int[][] arr = new int[r+2][c+2];
        for(int i = 0; i < r+2; i++) {
            arr[i][0] = 1;
            arr[i][c+1] = 1;
        }
        for(int j = 0; j < c+2; j++) {
            arr[0][j] = 1;
            arr[r+1][j] = 1;
        }

        int col = 1;
        int row = 1;
        int waitNum = 1;

        boolean flag = false;
        while(waitNum <= r * c) {
            if(waitNum == k) {
                flag = true;
                break;
            }

            arr[col][row] = 1;
            int ny = col + dy[direction];
            int nx = row + dx[direction];
            if(arr[ny][nx] == 1) {
                direction = (direction + 1) % 4;
            }

            col = col + dy[direction];;
            row = row + dx[direction];
            waitNum++;
        }

        if(flag) bw.write(col + " " + row + "\n");
        else bw.write("0\n");

        br.close();
        bw.flush();
        bw.close();
    }
}

아이디어를 생각해내기까지 많은 시간이 필요로 했지만, 구현된 코드를 보면 굉장히 단순하다는 것을 알 수 있다.