[BOJ_Python]1913. 달팽이

문제

https://www.acmicpc.net/problem/1913

 

사용 알고리즘

구현

 

풀이

고려사항

1. 방향 변경 타이밍 확인

2. 방향 변경

 

후기

1. 내가 처음 푼 풀이는 조건이 너무 까다로워 다른 풀이를 찾던 중 더 깔끔한 조건의 풀이를 발견했다.

 

2. 우선, 나의 풀이는 안쪽 가운데 1부터 시작하여 시계방향으로 이동한다.

방향을 제공하며 step을 확인하며 방향 변화 여부를 확인하고, flag를 확인하며 step의 수를 늘린다.

우선 가야하는 step은 방향전환 2번마다 1씩 증가한다.

때문에 Flag를 두어 방향 전환 시마다 토글 형식으로 변경하고 확인하였다.

3. 마지막 출력 시 하나하나 for문을 돌며 해당 숫자가 target이 맞는 지 확인하며 출력하는 것보다

배열을 채울 때 확인해서 저장해두고 배열 출력은 join을 사용하여 한 줄씩 출력하는 것이 시간에서 더 강점이 있었다.

 

4. 더 깔끔한 조건의 다른 풀이는 밖에 마지막 수(N * N)부터 시작하여 반시계 방향으로 채워가는 것이다.

이건 step을 확인 할 필요가 없기 때문에 step, flag 모두 사용되지 않는다.

오직 배열 범위를 넘어가지 않는지와 이미 채워져있는(방문한) 곳인지만 확인한다.

이미 방문했거나 배열의 범위를 넘어가면 방향을 변경해주면 되기 때문에

몇 칸을 이동할 수 있는지, 현재 몇 칸을 이동했는지 확인하지 않아도 된다.

 

 

코드

1. 처음 내 풀이

import sys
input = sys.stdin.readline

direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]

N = int(input())
target = int(input())

arr = [[0] * N for _ in range(N)]
arr[N // 2][N // 2] = 1

cur = 1
c_di = 0
ci, cj = N // 2, N // 2
step, c_step = 1, 0
flag = False

answer = [1, 1]

while cur < N * N:

    if arr[ci][cj] == target:
        answer = [ci + 1, cj + 1]

    ci, cj = ci + direction[c_di][0], cj + direction[c_di][1]
    cur += 1
    arr[ci][cj] = cur
    c_step += 1

	# 방향 변경
    if c_step == step:
        c_step = 0
        c_di = (c_di + 1) % 4
        # step 증가여부 확인
        if flag == True:
            flag = False
            step += 1
        else:
            flag = True

for i in range(N):
    print(" ".join(map(str, arr[i])))
print(" ".join(map(str, answer)))

 

2. 더 깔끔한 풀이

N = int(input())
target = int(input())

arr = [[0] * N for _ in range(N)]

directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
d_idx = 0

num = N * N
x = y = 0
answer = []
while num > 0:
    arr[x][y] = num
    if num == target:
        answer = [x+1, y+1]
    num -= 1

    dx, dy = directions[d_idx % len(directions)]
    nx, ny = x + dx, y + dy
    if nx < 0 or nx >=n or ny <0 or ny >=n or arr[nx][ny] != 0:
        d_idx += 1
        dx, dy = directions[d_idx % len(directions)]
        x, y = x + dx, y + dy
    else:
        x, y = nx, ny

for i in range(N):
    print(" ".join(map(str, arr[i])))
print(" ".join(map(str, answer)))

 

 

결과