[SWEA] 달팽이 숫자(1954) - Python(DFS)

숫자 N을 출력받아 N*N 배열에 달팽이처럼 들어갈 숫자를 출력하는 문제이다.

 

SW Expert Academy

---

테이스 케이스

 

[TC1]

입력 : 3

출력 :

1 2 3
8 9 4
7 6 5

 

[TC2]

입력 : 4

출력 :

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

 

---

해결 과정

문제를 보자마자 달팽이 숫자라는 조건에 맞는 이어진 길을 찾는 문제기 때문에 DFS로 해결하면 좋겠다고 생각했다.배열의 끝에 도달할 때마다 해당 방향에서 시계방향으로 돌아가고 있다. 그래서 방향 [ 우, 하, 좌, 상 ]을 나타내는 방향 리스트를 만들고, 새로운 지역을 시작할 때마다 4방향을 차례대로 확인하고, 방문하지 않았으면 방문하는 식으로 해결했다.

 

---

코드

T = int(input())
MAX = 10 + 10

def dfs(y, x):
    global map_, answer, dx, dy
    map_[y][x] = answer
    answer += 1

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if not map_[ny][nx] and 0 < nx <= N and 0 < ny <= N:
            dfs(ny, nx)

for test_case in range(1, T+1):
    N = int(input())

    map_ = [[0] * MAX for _ in range(MAX)]

    answer = 1

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

    dfs(1, 1)

    print(f'#{test_case}')
    for y in range(1, N+1):
        print(*map_[y][1:N+1])

 

주석처리

T = int(input()) # TC 개수
MAX = 10 + 10 # 전체 map_의 최대 경우를 고려해 지도 생성

def dfs(y, x): # dfs 정의
    global map_, answer, dx, dy # 각 변수를 전역으로 사용
    map_[y][x] = answer # 해당 위치에 answer(방문 순서)를 기록
    answer += 1

    for i in range(4): # 우, 하, 좌, 상 방향으로 탐색
        nx = x + dx[i] # 다음 x 값
        ny = y + dy[i] # 다음 y 값
        if not map_[ny][nx] and 0 < nx <= N and 0 < ny <= N: # 방문하지 않았고, 범위 안이라면
            dfs(ny, nx) # 해당 좌표 방문

for test_case in range(1, T+1): # TC 동안
    N = int(input()) # N 입력 받음

    map_ = [[0] * MAX for _ in range(MAX)] # MAX를 고려한 지도 리스트 생성

    answer = 1 # 정답 1로 초기화

    dx = [1, 0, -1, 0] # x의 움직임
    dy = [0, 1, 0, -1] # y의 움직임

    dfs(1, 1) # 1,1을 dfs로 탐색

    print(f'#{test_case}')
    for y in range(1, N+1):
        print(*map_[y][1:N+1]) # 리스트 형태를 없애고 출력