[백준] 자리배정 - Python 파이썬

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

사용개념: 그리디

 

1. 시간복잡도

최악의 경우 모든 좌석을 방문해야 하므로 O(C*R)이다. 5 ≤ C, R ≤ 1,000 이므로 시간 내 계산 가능하다. 

 

2. 풀이

• 2차원 배열에서 나선형 패턴으로 좌석을 배정한다. 
• 방향 벡터를 사용하여 위, 오른쪽, 아래, 왼쪽 순서로 이동한다. 
• 배열의 범위를 벗어나거나 이미 방문한 위치를 만나면 방향을 바꾼다. 

def find_seat(C, R, K):
    if K > C * R: return 0
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    
    seats = [[0] * C for _ in range(R)]
    x, y = 0, 0
    direction = 0
    
    for num in range(1, K + 1):
        if num == K:
            return x + 1, y + 1
        
        seats[y][x] = num
        nx, ny = x + dx[direction], y + dy[direction]
        
        if nx < 0 or nx >= C or ny < 0 or ny >= R or seats[ny][nx] != 0:
            direction = (direction + 1) % 4
            nx, ny = x + dx[direction], y + dy[direction]
        
        x, y = nx, ny
    
    return 0

C, R = map(int, input().split())
K = int(input())

result = find_seat(C, R, K)
if result == 0:
    print(0)
else:
    print(result[0], result[1])

 

3. (x, y) 좌표계 ⇔ 2차원 배열

• 일반적인 (x, y) 좌표계
  • x: 열, y: 행

• 2차원 배열
  • grid[행][열]

• 문제에서 R, C
  • R: 행, C: 열

 

- 이미지 출처: https://good-potato.tistory.com/84