[백준] 10157. 자리배정 (Java)

문제

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

10157번: 자리배정

 

풀이

0. 문제 해석

일반적인 구현 문제로 달팽이 배열 문제들과 유사하다.

 

자리배정 규칙을 보면 상, 우, 하, 좌 순으로 방향이 바뀌는 것을 알 수 있다.

위와같이 테두리를 -1로 표기한 배열을 만들어서 내가 다음에 이동할 방향이 0이 아니라면(벽이거나 이미 데이터가 있다면) 방향을 전환해주며 반복한다.

 

그러다가 현재 값이 k와 같다면 리턴해주고 좌표를 출력한다.

 

1. 좌석 배열 선언

테두리를 -1 처리해주고 가로세로의 곱보다 k가 크다면 배정할 수 없으므로 예외처리 해준다.

 

2. 좌석 배치

델타 탐색으로 상우하좌 순으로 반복하며 좌석을 하나씩 입력한다.

대기번호 k 관객의 좌석을 만났다면 리턴해주는데, 배열의 인덱스와 좌석배치가 반대이므로 계산하여 출력해준다.

 

3. 전체 코드

// [백준] 10157. 자리배정 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	// 상우하좌
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,1,0,-1};

    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[][] arr = new int[r + 2][c + 2];

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

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

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

    	// 좌석을 배정할 수 없는 경우
    	if(k > c * r) {
    		System.out.println(0);
    		return;
    	}

    	int x = r; // 현재 x 좌표
    	int y = 1; // 현재 y 좌표
    	int value = 1; // 좌석
    	int dir = 0; // 방향 (상우하좌 => 0123)

    	while(true) {
    		arr[x][y] = value;
    		// 대기번호 k 관객 좌석 위치 출력
    		if(value == k) {
    			System.out.println(y + " " + (r - x + 1));
    			break;
    		}

    		// 이미 채워져있거나 벽을 만날때마다 방향 전환
    		if(arr[x + dx[dir]][y + dy[dir]] != 0) {
    			dir = (dir + 1) % 4;
    		}
    		x += dx[dir];
    		y += dy[dir];

    		value++;

    		// 좌석 최대
    		if(value > c * r) {
    			break;
    		}
    	}

//    	// 좌석 배치 확인
//    	for(int i = 0; i < r + 2; i++) {
//    		for(int j = 0; j < c + 2; j++) {
//    			System.out.print(arr[i][j] + " ");
//    		}
//    		System.out.println();
//    	}
    }
}