BOJ 10157 자리배정

문제 탐색하기

• 가로로 C만큼, 세로로 R만큼의 좌석 배정이 가능하다.
• 첫번째 사람은 맨 왼쪽 아래에 배정한다.
• 이후 시계방향으로 돌면서 자리를 배정한다.
• K번째 순서 사람에게 배정될 자석 번호를 배정한다.
• 좌석이 배정될 수 없는 경우, 0을 출력한다.

코드 설계하기

구현 방법

• Early Return으로 좌석이 배정될 수 없는 경우 ( C X R < K ) 0을 출력한다.
• 0, R - 1번째 위치에서 탐색을 시작한다.
  • 시계 방향으로 돌면서 탐색하도록 한다.(상, 우, 하, 좌)
  • 방문한 위치는 탐색하지 않는다.
• 실제 배열의 x, y 시작점 위치는 세로 방향 (R)이 반대이므로, 좌표 값 연산을 보다 쉽게 하기 위해 y 방향을 반전시켜 계산한다.
  • 반시계 반향으로 돌면서 탐색한다. (하, 우, 상, 좌)
  • 매 iteration 마다 K 값을 감소시키고, K 값이 1이 되면 해당 위치 값의 x 값과 y 값을 리턴한다.

시간 복잡도

• 최대 O( C x R ) 값까지 순회가 가능하므로,
• 최대 연산 횟수는 1,000,000 이다.
  • 따라서 시간 내에 연산이 가능하다.

정답 코드 (Java)

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class b10157 {  
    private static int C, R, K;  
    private static boolean[][] map = new boolean[1001][1001];  
    private static int[] dx = {0, 1, 0, -1};  
    private static int[] dy = {1, 0, -1, 0};  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        C = Integer.parseInt(st.nextToken());  
        R = Integer.parseInt(st.nextToken());  
  
        st = new StringTokenizer(br.readLine());  
        K = Integer.parseInt(st.nextToken());  
  
        if ( K > C * R ) {  
            System.out.println("0");  
            return;  
        }  
  
        if ( K == 1 ) {  
            System.out.println("1 1");  
            return;  
        }  
  
        int x = 1, y = 1, dir = 0;  
        map[x][y] = true;  
  
        while (K != 1){  
            int nx = x + dx[dir];  
            int ny = y + dy[dir];  
  
            if (nx <= 0 || ny <= 0 || nx > C || ny > R || map[nx][ny]) {  
                dir = (dir + 1) % 4;  
                nx = x + dx[dir];  
                ny = y + dy[dir];  
            }  
  
            map[nx][ny] = true;  
  
            x = nx;  
            y = ny;  
            K--;  
        }  
  
        System.out.println((x) + " " + (y));  
    }  
}