[알고리즘 문제] Seat

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int width = sc.nextInt(); // 공연장의  가로길이
        int height = sc.nextInt();  // 공연장의 세로길이
        int order = sc.nextInt(); // 대기순서
        int direction = 1;
        int x = 0, y = -1;
        boolean down = true, up = false, right = false, left = false; // 시계방향으로 탐색할 수 있도록 도와주는 변수

        int[][] ary = new int[height][width]; // 공연장의 좌석배열

        if (order > width * height) { // 공연장의 좌석보다 대기순서가 크게 되면 0을 출력하고 return
            System.out.println(0);
            return;
        }

        for (int i = 1; i <= order; i++) { // 대기순서 만큼 반복

            if (down && y + 1 < height && ary[y + 1][x] == 0) { // 아래쪽으로 탐색
                ary[y + 1][x] = i + 1;
                y++;
                continue;
            } else { // 아래쪽이 다 탐색이 끝나면 오른쪽으로 이동해야 하기 때문에 right를 제외하고 모두 false
                down = false;
                up = false;
                right = true;
                left = false;
            }

            if (right && x + 1 < width && ary[y][x + 1] == 0) { // 오른쪽으로 탐색
                ary[y][x + 1] = i + 1;
                x++;
                continue;
            } else { // 오른쪽 탐색이 모두 끝나면 위쪽으로 이동해야 하기 떄문에 up을 제외하고 모두 false
                down = false;
                up = true;
                right = false;
                left = false;
            }
            if (up && y - 1 >= 0 && ary[y - 1][x] == 0) { // 위쪽으로 탐색
                ary[y - 1][x] = i + 1;
                y--;
                continue;
            } else { // 위쪽 탐색이 모두 끝나면 왼쪽으로 이동해야 하기 때문에 left를 제외하고 모두 false
                down = false;
                up = false;
                right = false;
                left = true;
            }
            if (left && x - 1 >= 0 && ary[y][x - 1] == 0) { // 왼쪽으로 탐색
                ary[y][x - 1] = i + 1;
                x--; 
                continue;
            } else { // 왼쪽 탐색이 모두 끝나면 아래쪽으로 이동해야 하기 때문에 down을 제외하고 모두 false
                i--; // 아래쪽으로 탐색하는 로직(첫번쨰 if문)이 제일 위쪽에 있어서 i변수를 --해주어여함.
                down = true;
                up = false;
                right = false;
                left = false;
            }

        }

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

}

이 문제는 공연장(2차원 배열로 표현)을 위의 사진을 기준으로 0,0부터 시계방향으로 회전하면서 대기순서가 k번째인 관객은 앉게되는 x,y좌표를 구하는 문제이다. 만약 대기순서 k가 공연장의 좌석보다 큰 경우는 0을 출력핳게 된다.

 

아이디어는 k번째 좌석의 좌표를 구하는 문제이니, for문을 k번반복한다. 사진에서는 왼쪽아래부분을 0,0으로 잡고 하였지만 배열에서는 왼쪽위부분을 0,0을 기준으로 탐색을 시작한다. 시계방향이라고 하였지만 실제 사진과 배열의 y위치는 180도 뒤집힌 모양이다. 따라서 실제 탐색을 할때는 0,0(왼쪽위)를 기준으로 반시계 방향으로 탐색한다.

 

순서는 아래,오른쪽,위쪽,왼쪽,아래....순으로 반복을 하게된다. 총 4개의 if문 조건의 첫번째 변수인 down,right,up,left는 어디방향으로 탐색할 건지 결정한다. 만약 down이 true인 경우 다른 변수들은 모두 false가 되고 for문에서 down이 true이 if문만 걸리게 된다. 

 

if문의 두번쨰 변수는 가장 가장자리에 있는 값이 배열을 넘어가는 경우를 체크하기 위함히고, 세번쨰 변수는 탐색하는 타음 위치에 0(체크하지 않은 좌석, 탐색할 수 있는 경우)이 있는지 없는지 체크하게 된다. 만약 탐색할 수 없는 경우, 즉 false가 되면 끝까지 탐색한 경우 이므로 다음 방향을 탐색하게 된다. 이떄 처리되는 부분은 else에서 다음 탐색할 방향의 위치 변수값을 true로 하고 전부 false로 해준다.

 

이렇게 되면 다음 for문에서 if의 첫번째 변수가 true인 곳만 골라서 다시 탐색하게 된다.