문제

' 10157번 자리배정 '
https://www.acmicpc.net/problem/10157

풀이

조건

• 가로로 C개, 세로로 R개의 좌석이 C×R격자형으로 배치되어있다.
• (1,1)에서 위쪽 방향의 좌석으로 올라가면서 다음 사람들을 배정한다. 만일 더 이상 위쪽 방향으로 빈 좌석이 없으면 오른쪽으로 가면서 배정한다. 똑같은 형식으로 아래쪽, 왼쪽으로 가면서 남은 빈 좌석을 배정한다.
• 대기번호 K인 관객에게 배정될 좌석번호 (x,y)를 구해서 두 값, x와 y를 하나의 공백을 사이에 두고 출력한다.
• 만일 모든 좌석이 배정되어 해당 대기번호의 관객에게 좌석을 배정할 수 없는 경우에는 0(숫자 영)을 출력해야 한다.

풀이 순서

• C, R, K를 입력받고 방문체크 해줄 배열을 만들어준다.
• 방향을 dx, dy로 정리해서 범위안에서 지난간 점을 제외하고 방문체크 하면서 이동할 수 있도록 함수를 만들어 준다.
• 이동할 때마다 tmp를 +1 해주어 K 에 도달하면 멈추고 x, y값을 출력할 수 있도록 한다.

Check point

• dx, dy가 어디까지 가는지 확인하고 적합한 방문체크 배열을 만들어준다.
• 어떤 상황에서 방향을 바꿔줄지 고려해야 한다.
• x, y가 1, 1부터 시작한다.

코드

Python

def func(x, y):
    global arr
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    tmp = 1
    i = 0
    while True:
        if tmp == K:  # K번째 사람이면 멈추기
            return x + 1, y + 1  # x,y가 1,1 부터 시작하므로
        arr[y][x] = True  # 지나간 점 체크
        nx = x + dx[i]
        ny = y + dy[i]
        if (0 <= nx < C and 0 <= ny < R):  # 다음 점이 범위안이고
            if arr[ny][nx] != True:  # 지나간 점이 아니라면
                x = nx  # 이동하기
                y = ny
                tmp += 1
            else:  # 지나간 점이면 방향 바꾸기
                i = (i + 1) % 4
        else:  # 다음 점이 범위를 벗어나면 방향 바꾸기
            i = (i + 1) % 4


C, R = map(int, input().split())
K = int(input())
arr = [[False for _ in range(C + 1)] for _ in range(R + 1)]  # 다음점까지 고려해서 1개씩 더 큰 배열 만들기
if K > C * R:
    print(0)
else:
    print(*func(0, 0))

다른 방법

def move(x,y):
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    visit = [[False]*C for _ in range(R)]
    k = 0
    for i in range(1,C*R+1) :
        if i == K:
           return (x+1,y+1)
        else:
            visit[y][x] = True
            x += dx[k]
            y += dy[k]
            if x<0 or y<0 or x>=C or y>=R or visit[y][x]:
                x -= dx[k]
                y -= dy[k]
                #범위 벗어나면 뒤로 뺐다가 방향 바꿔서 전진 
                k = (k+1)%4
                x += dx[k]
                y += dy[k]


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

#좌석을 줄 수 없는 경우 
if K > C*R :
    print(0)
    exit() #아예끝내기

print(*move(0,0))