[python] 백준 1913 - 달팽이

출처 : 백준, https://www.acmicpc.net/problem/1913

1913번: 달팽이

 

와 이제 실버 1이다~

 

 

풀이

 

#정사각형 테두리 채우기

point = None

def fillBorder(left_top, right_bottom, map, target):
  global point
  s_i, s_j = left_top
  e_i, e_j = right_bottom
  length = (e_j - s_j + 1) * 4 - 4
  number = (e_j - s_j + 1)**2

  di = [1, 0, -1, 0]
  dj = [0, 1, 0, -1]

  index = 0

  i = s_i
  j = s_j

  while True:
    if number == target:
      point = (i + 1, j + 1)

    if map[i][j] != 0:
      break
      
    map[i][j] = number
    number -= 1
    i, j = i + di[index], j + dj[index]
    
    if (i, j) in [(s_i, e_j), (e_i, e_j), (e_i, s_j)]:
      index += 1

n = int(input())
target = int(input())
map = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n//2 + 1):
  fillBorder((i, i), (n-i-1, n-i-1), map, target)

for line in map:
  print(*line)
print(*point)

 

정사각형 배열의 왼쪽 상단, 오른쪽 하단 좌표를 받아서 회전 방향대로 채우는 알고리즘이다.

point를 global 변수로 빼서 target과 일치하면 따로 저장하도록 만들었다.

---

 

시간 복잡도

 

O(N^2)

 

알게 된 점

 

-

 

고찰

 

이 문제처럼 회전형으로 채우는 방법 중 더 좋은 방법이 뭐가 있을까 찾아봤는데

일단 내가 한 것처럼 테두리마다 채우는 게 보편적인 방법인 듯 하다.

 

Github

백준 1913 - 달팽이