백준 - 1913번 달팽이

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

1913번: 달팽이

이 문제는 알고리즘 분류가 구현이다.

그냥 원하는 아웃풋이 나오게 구.현. 하면 되는 문제이다.

 

문제에서는 정사각형의 표에서 가운데 좌표에 1이 들어가고 달팽이 등껍질 그리듯이 뱅글뱅글 돌면서 숫자를 1씩 키워서 값을 넣은 표와 인풋으로 받은 숫자의 좌표를 출력하라고 한다.

 

처음에는 1의 좌표를 계산해서 1부터 숫자의 크기를 늘려주려고 했는데, 시작 좌표가 (0,0) 이면 당연히 생각하기 더 편하지 않을까?

그리고 (0,0)의 값은 언제나 N의 제곱이기 때문에, 나는 (0,0)에 N 제곱을 넣어주고 숫자의 크기를 1씩 줄이면서 뱅글뱅글 돌기로 했다.

 

❗️이동할 때 확인해야 하는 사항들❗️

•  현 위치에서 상하좌우의 값 확인을 통해 이동방향 결정
• 2차원 배열 밖으로 나가지 않는지 (not out ouf index)
• 값이 0 인지 아닌지 (0 이라면 값을 바꿔주어야 하는 자리이고, 0 이라면 이미 값을 바꿔준 자리이기 때문에 이동 X)
• 이동 가능햔 방향이 여러 방향이라면, 현재 이동방향을 우선순위로 갖음

 

1. 결과로 출력해야 하는 2차원 배열의 (0,0) 의 값은 N 제곱으로 바꿔주고, 이동방향은 아래로 설정한다.

2. 이동방향으로 한 칸 이동할 때마다 -1 한 값을 넣어준다.

3. 값을 넣어줄 때, 인풋에서 원하는 숫자와 같다면 해당 좌표를 기억해둔다.

 

구현 문제이기 때문에 위의 로직을 코드로 동작하게 짜기만 하면 되는데, 로직을 생각해 놓고 나니까 이 부분은 크게 어렵지 않았다.

다만 몇가지 고려하지 못한 부분들이 있었다.

 

첫 번째로 반복문의 범위 설정에서, 마지막 숫자인 1을 채우고 나서 반복이 종료되어야 하는데 범위 설정을 잘못해서 통과하지 못했다.

두 번째로는, 좌표값을 요구하는 인풋 숫자가 N 제곱인 경우를 고려하지 못해서 통과하지 못했다.

예를 들어 N 이 5 이고, 좌표값을 원하는 숫자가 25일때의 좌표를 출력하지 못했다.

그 이유로는, 코드를 짤 때 반복문 안에서 돌다가 원하는 숫자일때 좌표를 기억하게 했는데 N 제곱의 경우 반복문 시작 전부터 이미 값이 채워져 있기 때문에 이 로직을 타지 않기 때문이다.

 

이 부분에 대한 해결방법으로는 반복문 돌기 전에 좌표를 원하는 숫자가 N 제곱인지 아닌지 확인하는 조건문을 추가했다.

반복문 안에서 N 제곱의 좌표에 대한 고려도 할 수도 있지만, 이렇게 로직을 생각해내기가 좀 귀찮았다.

그래서 그냥 초반에 확인 한번 하고 넘어가는걸로,, 

 

그래서 최종 제출한 코드는 아래와 같다.

n = int(input())
target = int(input())

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

start_num = n ** 2

if target == start_num:
    target_position = [0, 0]
else:
    target_position = []

directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
cur_direction = directions[0]

position = [0, 0]
mat[0][0] = start_num

for i in range(start_num, 1, -1):
    possible_direction = []
    for j in range(len(directions)):
        next_position = [x+y for x,y in zip(position, directions[j])]

        a, b = next_position
        if a < 0 or a >= n or b < 0 or b >= n:
            pass
        else:
            next_position_value = mat[a][b]

            if next_position_value > 0:
                pass
            else:
                possible_direction.append(directions[j])

    if len(possible_direction) > 1:
        cur_direction = cur_direction
    else:
        cur_direction = possible_direction[0]

    position = [x+y for x,y in zip(position, cur_direction)]

    x, y = position

    mat[x][y] = i -1

    if mat[x][y] == target:
        target_position = [x, y]

for i in range(len(mat)):
    values = (' ').join(map(str, mat[i]))
    print(values)

x, y = target_position
print(x+1, y+1)

 

시간 복잡도는 N X N 2차원 배열에 값들을 채워나가기 때문에 N 제곱이라고 생각했다.

처음에 2차원 배열 셋팅하는 부분은 확실히 N 제곱인데, 실제로 값을 채워나가는 부분은 N 이라서 정확한 시간복잡도는 어떻게 되는건지 사실 잘 모르겠다!