백준 10157번 자리배정 파이썬

리뷰

실버4 문제가 맞나 싶을 정도로 어려웠다. 구현 문제는 시간이 오래 걸려 기피했었는데 자주 풀어봐야 할 것 같다.

문제 풀이

• 1. 2차원 배열을 r * c 크기로 생성해 준다.
• 2. x, y 좌표를 초기 시작 위치인 0, 0으로 초기화
• 3. 방향을 나타낼 배열을 생성해 주고 초기 index값을 할당해 준다. 처음엔 y방향으로 1씩 이동이니 (0, 1)이 되어야 한다.
• 4. 관객의 번호를 나타낼 변수를초기화 해 준다.

찾고 싶은 관객의 번호가 자리를 벗어나면 바로 print(0)후 리턴해 주면 된다. 아닐 경우 while 루프를 돌아 관객의 번호가 지정된 자리를 찾을 경우 x + 1, y + 1값을 리턴해 준다.

 

우선 x, y 좌표에 자리를 지정해 주고 다음 x, y 좌표를 찾아 준다.

현재 진행 방향으로 이동 후 x, y 좌표가 각각 음수이거나 가로 세로 범위를 넘어섰거나 다음 좌표값의 자리에 배정된 숫자가 있지 않을 경우 계속 진행해 준다.

만약 위에서 언급한 3가지 조건 중에 하나라도 해당 된다면 방향 인덱스에 1을 더한 후 4로 나누어 준다. 방향 배열을 순차적으로 작성 하였으므로 자동으로 다음 방향으로 이동하게 된다.

마지막으로 좌석 번호를 올려 주고 while 루프가 다시 돌게 된다.

참고 사항

while의 조건에서 크거나 같다는 조건을 해줘야 한다. <=가 아닌 <로 했다가 틀렸다.

출력 전에 x와 y값에 1을 더해 주어야 한다.

정답 코드

def q10157():
    # 백준 10157번 자리배정 파이썬
    c, r = map(int, input().split())
    k = int(input())
    if k > c * r:
        print(0)
        return
    dp = [[0] * r for _ in range(c)]
    direct = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    x, y = 0, 0
    index = 1
    direct_index = 1
    while index <= c * r:
        dp[x][y] = index
        if k == index:
            print(x + 1, y + 1)
            return
        next_x = x + direct[direct_index][0]
        next_y = y + direct[direct_index][1]
        if (0 <= next_x < c) and (0 <= next_y < r) and (dp[next_x][next_y] == 0):
            x, y = next_x, next_y
        else:
            direct_index = (direct_index + 1) % 4
            x += direct[direct_index][0]
            y += direct[direct_index][1]
        index += 1
q10157()