[파이썬/Python] 백준 10157번: 자리배정

숨·2024년 8월 25일

코테

알고리즘 문제 풀이

목록 보기

61/105

📌 문제 : 백준 10157번

📌 문제 탐색하기

C : 공연장 가로 크기 $( 5 ≤ C ≤ 1,000)$
R : 공연장 세로 크기 $( 5 ≤ R ≤ 1,000)$
K : 대기 순서 $(1 ≤ K ≤ 100,000,000)$

C×R격자형으로 배치된 좌석에서 각 좌석의 번호가 좌표 (x,y)로 표시될 때,
대기 순서가 K인 관객이 배정받을 좌석 번호 (x,y)를 찾는 문제이다.

문제 풀이

⭐️ 자리 배정 방법

기다리는 순서대로 대기번호 받는다.

(1,1)부터 비어있는 좌석에 시계 방향으로 돌아가며 관객을 배정한다.

배정 받은 좌석이 없는 경우 0을 출력한다.

총 좌석의 수는 C*R 값이므로 만약 K가 이 값보다 크다면 배정받을 수 있는 자리가 없다.
→ 바로 0을 출력한다.

⭐️ 격자 내에서 움직일 수 있는 방법

4가지 방향 : 상하좌우

시계 방향으로 이동해야 하므로 이동할 수 없는 칸을 마주칠 때마다 움직이는 방향을 바꿔야 한다.

위쪽 → 오른쪽 → 아래쪽 → 왼쪽

헷갈리지 않도록 인덱스와 좌표를 동일하게 하기 위해 (C+1)×(R+1)의 2차원 배열을 만든다.
인덱스가 (1, 1), (C, R)을 벗어나지 않도록 움직일 수 있는 방법을 고려해 이동하면서,
카운트를 세어 반복 내에서 카운트가 K가 될 때까지 움직이도록 한다.
이 때, 시작 위치는 C×R 격자의 맨 왼쪽 아래로 (1, 1)이 될 것이다.

가능한 시간복잡도

격자 내 탐색 → $O(C * R)$

최종 시간복잡도
$O(C * R)$ 로 최악의 경우 $O(10^6)$ 이 되어 1초 내 연산 가능하다.

알고리즘 선택

전체 격자내를 조건에 따라 움직이면서 K번째의 좌표 찾기

📌 코드 설계하기

C, R 입력
K 입력
만약 K가 배정받을 자리가 없다면 바로 0 출력
격자 정의
이동 방향 정의
초기 위치 정의
이동
조건에 따라 이동 방향 바꾸기
결과 출력

📌 시도 회차 수정 사항

1회차

예제 1의 출력이 계속 (7,1)이 나와서 코드를 확인해보니, 맨 처음엔 이동하지 않고 한명을 배치하기 때문에 count = 1부터 시작해야 하는데 0부터 시작해서 수정하였다.

2회차

변경해도 출력이 이상해서 문제를 다시 확인해보니 시작점인 맨 왼쪽 아래 좌표가 (1, 1)인데 (1, R)로 두고 구현해서 잘못된 출력이 나왔다.

📌 정답 코드

import sys

input = sys.stdin.readline

# C, R 입력
C, R = map(int, input().split())

# K 입력
K = int(input())

# 만약 K가 배정받을 자리가 없다면 바로 0 출력
if K > C * R:
    print(0)

else:
    # 격자 정의
    grid = [[0] * (C + 1) for _ in range(R + 1)]

    # 이동 방향 (이동 순서에 따라 작성)
    moves = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    # 배정 인원 셀 변수 정의
    count = 1

    # 시작 위치
    x, y = 1, 1

    # 시작 방향 (위쪽)
    move = 0

    while True:
        grid[y][x] = count

        # 이동
        nx, ny = x + moves[move][0], y + moves[move][1]

        # 움직이는 방향 바꾸기
        if nx < 1 or ny < 1 or nx > C or ny > R or grid[ny][nx] != 0:
            move = (move + 1) % 4
            nx, ny = x + moves[move][0], y + moves[move][1]

        if count == K:
            # 결과 출력
            print(x, y)
            break

        # 배정 후 카운트 증가
        x, y = nx, ny
        count += 1