[백준] 자리배정 (10157번)

난이도 : Silver3
Link : https://www.acmicpc.net/problem/10157
Tag : 구현, 브루트포스 알고리즘
풀이일자 : 2024년 8월 25일

📌 문제 탐색하기

C : 가로 크기
R : 세로 크기
K : 대기 번호

해당 문제는 공연장에 자리를 배정해야 하는데 배정하는 조건이 1,1자리에서 부터 위 -> 오른쪽 -> 아래 -> 왼쪽 순으로 자리를 배정하는 문제이다.

가능한 시간복잡도

C와 R 은 5보다 크고 1,000 보다 작으므로 최대로 될 수 있는 좌석의 크기는 1,000 x 1,000 = 1,000,000이므로 충분히 완전 탐색이 가능한 시간 복잡도를 가진다.

📌 문제 접근 방법

모든 경우의 수를 탐색 할 수 있는 시간복잡도를 가지고 있으므로 한명한명 자리를 배정해 주다가 K 번째 사람이 배정받는 자리를 출력해주면 되는 문제이다.

따라서 자리를 배열로 만들어 놓고 자리를 탐색할때 갈 수 있는 4방향의 위치 설정을 해주고 갈 수 있을때와 갈 수 없을 때 조건 처리를 해준다면 이 문제는 쉽게 해결 가능할 것으로 확인된다.

📌 코드 설계하기

1. C,R,K 를 입력받는다.
2. 자리를 탐색 할 수 있는 함수를 작성한다.
   • 만약 K > C x R일때는 배정 할 수 없으모로 0
   • 갈 수 있는 방향 4방향을 dir_list에 저장한다.
   • x,y를 0으로 처음위치를 설정한다.
   • dir = 0 으로 방향을 설정한다
   • K만큼 for 문을 반복하여 자리를 탐색한다.
   • 만약 i 가 K일때 해당 자리를 return하고
   • 다음 자리를 탐색했을때 갈 수 없는 자리라면 dir를 수정하여 방향을 재설정한다.
3. answer에 함수 결과값을 저장한다.
4. answer가 0 이라면 배정할 수 없으므로 0을 출력한다.
5. answer가 0이 아니라면 x,y의 좌표값을 저장한 answer[0], answer[1] 을 출력한다.

📌 시도 회차 수정 사항

📌 정답 코드

C, R = map(int, input().split())  # C : 가로 R :세로
K = int(input())


def find_seat(C, R, K):
    if K > C * R:
        return 0

    seats = [[0] * C for _ in range(R)]
    dir_list = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 4방향 설정
    x, y = 0, 0  # 처음 위치
    dir = 0  # 방향 설정

    for i in range(1, K + 1):
        seats[y][x] = i  # 지나간 자리 체크

        if i == K:  # 해당 자리이면 return
            return (x + 1, y + 1)

        nx, ny = x + dir_list[dir][0], y + dir_list[dir][1]  # 다음 자리 탐색

        # 만약 다음 자리가 갈 수 없는 곳일때 조건 처리
        if nx < 0 or nx >= C or ny < 0 or ny >= R or seats[ny][nx] != 0:
            dir = (dir + 1) % 4  # 방향 설정
            nx, ny = x + dir_list[dir][0], y + dir_list[dir][1]  # 다음 자리 재 탐색

        x, y = nx, ny  # 위치 설정


answer = find_seat(C, R, K)

if answer == 0:
    print(0)
else:
    print(answer[0], answer[1])