[Algorithm🧬] 백준 10157 : 자리배정

문제

빙글빙글 탐색을 해서 찾았는데,

3 4
12

의 경우가 문제였다.
내 코드상 한번에 4개를 다 돌기 때문에, 한쪽 방향으로 탐색이 끝나고 나면 전체가 끝났는지 확인해야 함. 근데 4번이나 반복하는 코드를 써줘야하서 좀 구림...

import sys

readl = sys.stdin.readline

def leftToRight(row, start, end):
    global num, sol
    for i in range(start, end + 1):
        seat[row][i] = num
        if num == k:
            sol = (row + 1, i + 1)
        num += 1

def upToDown(col, start, end):
    global num, sol
    for i in range(start, end + 1):
        seat[i][col] = num
        if num == k:
            sol = (i + 1, col + 1)
        num += 1

def rightToLeft(row, end, start):
    global num, sol
    for i in range(end, start - 1, - 1):
        seat[row][i] = num
        if num == k:
            sol = (row + 1, i + 1)
        num += 1


def downToUp(col, end, start):
    global num
    for i in range(end, start - 1, - 1):
        seat[i][col] = num
        if num == k:
            sol = (i + 1, col + 1)
        num += 1


h, w = map(int, readl().split())
k = int(readl())

seat = [[0] * w for _ in range(h)]
num = 1

startCol = 0
endCol = w - 1
startRow = 1
endRow = h - 1

sol = (0, 0)


for i in range(min(w, h) // 2 + 1):
    leftToRight(i, startCol, endCol)
    if num == w * h + 1:
        break

    upToDown((w - 1) - i, startRow, endRow)
    if num == w * h + 1:
        break

    rightToLeft((h - 1) - i, endCol - 1, startCol)
    if num == w * h + 1:
        break

    downToUp(i, endRow - 1, startRow)
    if num == w * h + 1:
        break


    startCol += 1
    endCol -= 1
    startRow += 1
    endRow -= 1

for i in range(h):
    for j in range(w):
        if seat[i][j] == k:
            sol = (i + 1, j + 1)

# for i in range(h):
#     print(seat[i])

if sol == (0, 0):
    print(0)
else:
    print(*sol)

코드 정리

를 해보았으나 그닥 만족스러운 정리는 아님...

for i in range(min(w, h) // 2 + 1):
    for idx, (rOrc, start, end) in enumerate([(i, startCol, endCol),
                             ((w - 1) - i, startRow, endRow),
                             ((h - 1) - i, endCol - 1, startCol),
                             (i, endRow - 1, startRow)]):
        func[idx](rOrc, start, end)
        if num == w * h + 1:
            break

    startCol += 1
    endCol -= 1
    startRow += 1
    endRow -= 1

풀이 를 참고하여 이렇게 푸는게 제일 깔끔해보임!

BFS 처럼 dx, dy 로 상하좌우 표시하는거.. 생각해내기...

import sys

readl = sys.stdin.readline


h, w = map(int, readl().split())
k = int(readl())

if k > h * w:
    print(0)
    sys.exit(0)

seat = [[0] * w for _ in range(h)]
seat[0][0] = 1

move = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 왼 -> 오 / 상 -> 하 / 오 -> 왼 / 하 -> 상

방향 = 0
x, y = (0, 0)
for i in range(2, k + 1):
    while True:
        dx, dy = move[방향]
        nx, ny = x + dx, y + dy
        if 0 <= nx < h and 0 <= ny < w and seat[nx][ny] == 0:
            print((nx, ny, i))
            seat[nx][ny] = i
            x, y = nx, ny
            break
        else:
            방향 = (방향 + 1) % 4



print(x + 1, y + 1)