Programmers / 정수를 나선형으로 배치하기 - bfs, 달팽이 / Python 파이썬

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 정수를 나선형으로 배치하기

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/181832

프로그래머스

 

문제 설명

양의 정수 n이 매개변수로 주어집니다. n × n 배열에 1부터 n2 까지 정수를 인덱스 [0][0]부터 시계방향 나선형으로 배치한 이차원 배열을 return 하는 solution 함수를 작성해 주세요.

---

제한사항

• 1 ≤ n ≤ 30

---

입출력 예nresult

4	[[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]
5	[[1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]]

---

입출력 예 설명

입출력 예 #1

• 예제 1번의 n의 값은 4로 4 × 4 배열에 다음과 같이 1부터 16까지 숫자를 채울 수 있습니다.

행 \ 열0123

0	1	2	3	4
1	12	13	14	5
2	11	16	15	6
3	10	9	8	7

따라서 [[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]를 return 합니다.

입출력 예 #2

• 예제 2번의 n의 값은 5로 5 × 5 배열에 다음과 같이 1부터 25까지 숫자를 채울 수 있습니다.

행 \ 열01234

0	1	2	3	4	5
1	16	17	18	19	6
2	15	24	25	20	7
3	14	23	22	21	8
4	13	12	11	10	9

따라서 [[1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]]를 return 합니다.

---

나의 풀이

 

달팽이기본 문제. 달팽이 진행 방향을 먼저 확인 하고, d % 4 해주면 된다.

 

방문처리와 동시에 달팽이 수를 저장하면 됨

from collections import deque

def solution(n):
    result = bfs(n)
    return result

def bfs(n):
    visited = [[-1] * n for i in range(n)]
    direct = ((0, 1), (-1, 0), (1, 0), (0, -1))
    visited[0][0] = 1
    start = (0, 0)
    d = 0
    i = d % 4
    queue = deque([start])
    cnt = 1
    while queue:
        if cnt == n * n:
            break
        qy, qx = queue.popleft()
        ny = direct[i][0] + qy
        nx = direct[i][1] + qx

        if 0 <= ny < n and 0 <= nx < n and visited[ny][nx] == -1:
            cnt += 1
            visited[ny][nx] = cnt
            queue.append((ny, nx))
        else:
            d += 1
            i = d % 4
            queue.append((qy, qx))
    return visited