[백준/Java] 10157번 : 자리배정

🌵 문제 분석

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

CxR 배열을 달팽이 모양과 같이 반 시계 방향으로 탐색하여 K번째가 될 때의 좌표를 출력하는 문제이다.

대기 번호(K) :

좌석 번호 :

입력 :

C (공연장 가로 길이) R (공연장 세로 길이)

K (대기 번호)

7 6
11

 

🌵 구현 아이디어

💡 (1, 1)에서 시작하여 배열을 K-1번 순회하기

(1, 1)에서 시작하여 위, 오른쪽, 아래, 왼쪽으로 배열을 K-1번 순회하면 좌석 번호를 찾을 수 있다.

(좌석이 최대 1,000,000개이므로 모든 좌석을 일일이 탐색해도 1초 안에 가능하다.)

7 6
11

이 경우 위쪽으로 5번, 오른쪽으로 5번 총 10번 이동하면 된다. 

좌석 번호는 (1+5, 1+5)=(6, 6)

 

✅ 탐색 방법

• (1, 1)에서 탐색을 시작하므로 총 K-1번 탐색해야 K번째 좌표에 도착한다.
• 만약 탐색 범위가 배열 밖을 벗어났거나 이미 탐색한 곳이라면 방향을 위->오른쪽->아래->왼쪽 순서로 바꿔준다.
• 만약 K가 R*C보다 크다면 배정할 수 없는 자리이므로 0을 출력한다.

🌵 시간 복잡도

R, C는 최대 1,000이므로 탐색 횟수는 최대 R*C = 1,000,000번이다. 따라서 제한 시간 (1초) 안에 연산 가능하다.

🌵 알고리즘

구현

🌵 오답 노트

• 좌석 번호의 초기값을 1, 1로 지정해서 틀렸다.
• 이동 방향의 행, 열 값을 반대로 지정해서 틀렸다.
• 이미 방문했거나 범위를 벗어난 경우를 처리할 때 방향을 바꾸고 다음 좌표를 새로 구하는 방법을 쓰는 게 아니라 현재 좌표를 이전 좌표로 되돌린 후 while문의 다음 턴으로 넘어가게 만들어서 cnt세는 부분, 방문 체크 하는 부분 다 오류가 발생했다. nx, ny를 따로 두고 x, y에 대입하니 구현하기 편해졌다.

🌵 코드 설계

1. 입력받고 탐색을 위한 초기값 세팅
   1. C, R, K를 입력받기
   2. CxR 크기의 배열 board 선언
   3. 좌석 번호 x=R-1, y=0로 초기값을 설정
   4. 방문 체크 배열 check 선언
2. 배정 불가능한 좌석 처리
   1. K>C*R이면 좌석을 배정받을 수 없기 때문에 0을 출력하고 리턴
3. 위, 오른쪽, 아래, 왼쪽 순서로 이동하는 방향 정의
   1. dx = {-1, 0, 1, 0};
   2. dy = {0, 1, 0, -1};
4. K-1번 반복하며 K번째 좌표 찾기
   1. 현재 좌표에서 다음 좌표를 구하기
   2. 이미 방문한 좌표이거나 범위를 벗어나면 방향을 바꿔서 다음 좌표를 구하기
   3. dx[dir], dy[dir]를 기존 좌표에 더해서 다음 좌표 업데이트
   4. 방문 체크, cnt++
5. 좌표 출력하기

🌵 정답 코드

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

public class Main {
    static int C, R, K;
    static boolean[][] check;

    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()); // 세로 길이
        K = Integer.parseInt(br.readLine()); // K번째 좌석

        // 좌석 개수보다 K가 크면 불가능
        if (K > C * R) {
            System.out.println(0);
            return;
        }

        check = new boolean[R][C];

        // 이동 방향 (상, 우, 하, 좌)
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        int x = R - 1, y = 0; // 시작 위치 (좌하단)
        int dir = 0; // 방향 인덱스
        int cnt = 1; // 첫 번째 자리 포함

        check[x][y] = true; // 방문 표시

        while (cnt < K) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            // 범위를 벗어나거나 이미 방문한 경우 방향 변경
            if (nx < 0 || nx >= R || ny < 0 || ny >= C || check[nx][ny]) {
                dir = (dir + 1) % 4; // 시계방향 회전
                nx = x + dx[dir];
                ny = y + dy[dir];
            }

            x = nx;
            y = ny;
            check[x][y] = true;
            cnt++;
        }

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