백준 10157 자리배정 파이썬 풀이

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

10157번: 자리배정

 

 

처음에 이렇게 생긴 좌석배치를 보고

파이썬 2차원 배열은 왼쪽 위부터 arr[0][0] 이니까

좌석을 뒤집어서

요런식으로 배열을 만든 후 설계를 했다.

 

일단 저렇게 숫자를 배치하는 문제는 SWEA의 달팽이 문제와 상당히 흡사하다.

 

https://gkim1011.tistory.com/11

SWEA 13704 달팽이 숫자

이 문제는 아래>오른쪽>위>왼쪽 이니까

 다이렉트 배열을

    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]

이렇게 만들어줬다.

 

while문을 돌면서

1) 배열 범위를 벗어나지 않고,

2) 이미 숫자가 채워진 곳을 또 채우지 않고,

3) 다이렉트 배열을 돌아가다가 아래>오>위>왼을 한바퀴 돌았으면 또 아래>오>.. 이렇게 돌게끔 설계하면 된다.

 

width, height = map(int, input().split())
find_number = int(input())
arr = [[0]*width for _ in range(height)]
idx =0
x, y = 0, 0
cnt = 1

while cnt <= width*height:
    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    arr[y][x] = cnt
    cnt +=1

    ny = y+dy[idx]
    nx = x+dx[idx]

    if ny>height-1 or nx>width-1 or nx<0 or ny<0 or arr[ny][nx] !=0:
        idx +=1

    if idx>3:
        idx =0


    y += dy[idx]
    x += dx[idx]

 

출력하는 부분은 2중 for문으로 그 사람이 어디 앉아있는지 인덱스만 출력하면 된다.

flg =0
for i in range(height):
    for j in range(width):
        if arr[i][j]== find_number:
            flg =1
            print(f'{j+1} {i+1}')

if flg == 0:
    print('0')

대기번호의 좌석이 없으면 flag로 따로 표시를 해주고,

좌석은 1,1 부터 있으니까 파이썬 인덱스에서 1씩 추가해주면 된다.

 

 

 

전체풀이)

width, height = map(int, input().split())
find_number = int(input())
arr = [[0]*width for _ in range(height)]
idx =0
x, y = 0, 0
cnt = 1

while cnt <= width*height:
    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    arr[y][x] = cnt
    cnt +=1

    ny = y+dy[idx]
    nx = x+dx[idx]

    if ny>height-1 or nx>width-1 or nx<0 or ny<0 or arr[ny][nx] !=0:
        idx +=1

    if idx>3:
        idx =0
        
    y += dy[idx]
    x += dx[idx]

flg =0
for i in range(height):
    for j in range(width):
        if arr[i][j]== find_number:
            flg =1
            print(f'{j+1} {i+1}')
if flg == 0:
    print('0')