1954. 달팽이 숫자문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PobmqAPoDFAUq

SW Expert Academy

 

BFS 활용

시작점은 무조건 (0, 0)

달팽이 무빙은 오른쪽, 아래, 왼쪽, 위쪽 순으로 이루어진다.

그래서 direction 리스트에 방향을 튜플로 순서대로 저장해준다.

direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
d = 0 # 현재 움직일 방향

이후 BFS를 direction에 따라 시행한다.

방향은 현재 direction에 따른 다음 위치가 map 크기를 넘어섰거나, 방문 노드인 경우 바꿔주었다.

d = (d + 1) % 4

 

# 전체 코드

#https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV5PobmqAPoDFAUq&categoryId=AV5PobmqAPoDFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

from collections import deque

T = int(input())

def bfs(map, size) :
    queue = deque([(0, 0)])
    map[0][0] = 1

    direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    d = 0
    while queue :
        now_r, now_c = queue.popleft()
        new_r, new_c = now_r + direction[d][0], now_c + direction[d][1]
        if 0 <= new_r < size and 0 <= new_c < size and map[new_r][new_c] == 0 :
            queue.append((new_r, new_c))
            map[new_r][new_c] = map[now_r][now_c] + 1
        else :
            d = (d + 1) % 4
            new_r, new_c = now_r + direction[d][0], now_c + direction[d][1]
        
            if map[new_r][new_c] == 0 :
                queue.append((new_r, new_c))
                map[new_r][new_c] = map[now_r][now_c] + 1
        
        
for t in range(1, T+1) :
    N = int(input())
    ans = [[0 for _ in range(N)] for _ in range(N)]
    print(f'#{t}')
    if N == 1 :
        print(1)
    else :
        bfs(ans, N)
        for n in range(N) :
            print(*ans[n])