프로그래머스, 정수를 나선형으로 배치하기

프로그래머스, 정수를 나선형으로 배치하기

 

https://school.programmers.co.kr/learn/courses/30/lessons/181832

프로그래머스

 

풀이

문제를 보자마자 백준 뱀 문제가 떠올랐다.

뱀 문제도 복습해야 겠다.

 

일단 방문표시를 해주시기 위해 0으로 배열을 초기화 해준다.

딱 방문하려고 봤을때 0이면 방문하면 되는 것!

result = [[0 for _ in range(n)] for _ in range(n)]

 

그리고 북동남서 모든 방향으로 갈수 있도록 방향과 백터를 표시해준다.

행열에서 (1,1)을 북쪽으로 이동시키면 (0,1)이 된다.

행열에서 (1,1)을 동쪽으로 이동시키면 (1,2)이 된다.

행열에서 (1,1)을 남쪽으로 이동시키면 (2,1)이 된다.

행열에서 (1,1)을 서쪽으로 이동시키면 (1,0)이 된다.

 

그리고 북동남서 순으로 index를 붙여준다.

북은 0 index, 동은 1 index, 남은 2 index, 서은 3 index

이 인덱스 순은 자신이 원하는 순으로 바꾸면 된다.

 

# 북동남서
dr = [-1,0,1,0]
dc = [0,1,0,-1]

# 방향 우회전
direction = (direction + 1) % 4
cr += dr[direction]
cc += dc[direction]

# 방향 좌회전
direction = (direction - 1) % 4
cr += dr[direction]
cc += dc[direction]

 

시뮬레이션 문제의  초기 설명은 위와 같이 해주면 된다.

그렇다면, 이 문제는 0행 0열에서 시작해 동쪽으로 이동하다가 방문한적이 있거나(값이 0이 아니거나) 배열 index 범위를 초과하면 우회전해주면 된다.

 

그래서 일단 next row와 next colunm을 구해주고 현재 방향으로 갈 수 있는지 판단후, 갈수 있으면 current row와 current colunm을 업데이트해주고 만약 현재 방향으로 갈 수 없으면 우회전 방향을 틀어준다.

 

이를 코드로 작성하면 다음과 같다.

 

나의 풀이

def solution(n):
    answer = [[0 for _ in range(n)] for _ in range(n)]

    # 북동남서
    dr = [-1, 0, 1, 0]
    dc = [0, 1, 0, -1]

    # 초기에 동쪽으로 가야함.
    direction = 1
    # 0행 0열에서 시작
    cr, cc = 0, 0

    # 총 이동 횟수 n의 제곱
    for i in range(n*n):
        answer[cr][cc] = i+1

		# 다음에 갈 곳
        nr = cr + dr[direction]
        nc = cc + dc[direction]

        if 0 <= nr < n and 0 <= nc < n and answer[nr][nc] == 0:
        	# 계속 현재 방향으로 갈 수 있는지
            cr = nr
            cc = nc
        else:
        	# 방향 우회전
            direction = (direction + 1) % 4
            cr += dr[direction]
            cc += dc[direction]
    return answer