https://www.acmicpc.net/problem/1022
1022번은 소용돌이 예쁘게 출력하기 입니다. 아! 이제부터 문제 설명은 위 페이지에 있으니 생략하려고요...ㅎㅎ 풀이 위주로 설명할게요!
Hint!
자잘하게 생각할거리가 많아서 차근차근 보도록 하겠습니다.
먼저 소용돌이는 문제에서 알려준 것처럼 중앙에서 출발해 숫자를 늘리며 나선형으로 배열되어 만들어집니다. 이해하는데 크게 어렵지는 않으나, 제 풀이에는 이 소용돌이를 어떻게 바라보느냐가 중요합니다. 행 번호는 r로, 열 번호는 c로 표현할 때, 아래는 -10 < r < 10, -10 < c < 10 까지 출력한 소용돌이의 모습입니다.
저는 level이라는 것을 먼저 정의하려고 합니다. level은 현재 소용돌이가 중심으로 부터 얼마나 떨어져 있는지를 의미합니다. 소용돌이의 가장 중심에 위치한 숫자 1을 level = 0이라고 정의를 하고 1을 중심으로 다음 소용돌이인 2~9까지의 숫자가 위치한 정사각형의 영역을 level = 1이라고 정의하는 겁니다. level = 2는? 다음 정사각형에 있는 10~25까지의 숫자를 의미합니다.
이렇게 했을 때, 몇가지 체크해 볼 수 있는 규칙은 다음과 같습니다.
- 각 level의 소용돌이는 -level <= r <= level, -level <= c <= level 영역의 테두리를 의미합니다.
- 각 level의 소용돌이의 가장 오른쪽 하단의 숫자는 (2 * level + 1) ^ 2와 같습니다.
아래 그림은 위 규칙을 더 잘 설명하기 위해 level = 2의 소용돌이를 가져온 것입니다.
level 2의 소용돌이의 숫자 17은 (-2, -2) 좌표, 25는 (2, 2) 좌표를 가지고 있죠. 즉, 1번 규칙인 "각 level의 소용돌이는 -level <= r <= level, -level <= c <= level 영역의 테두리를 의미합니다." 를 볼 수 있습니다. 그리고, 빨간 직사각형 내의 25라는 숫자는 현재 level인 2를 2번 규칙에 대입하여 구할 수 있습니다. (25 = (2 * 2 + 1) ^ 2)
이 두 규칙을 이용해 결과로 출력해야 할 영역의 숫자들을 구하려고 합니다. 아래의 그림을 먼저 보시고 이해해 볼게요!
빨간 테두리 안에 있는 숫자가 설명을 위해 예제로 삼은 목표 숫자들입니다. 입력을 -8 5 -5 7 을 입력해서 얻어야 하는 숫자들이죠. 파란 테두리 위에 있는 숫자들은 안에서부터 level이 5부터 8까지의 소용돌이 위에 있는 숫자들을 보여줍니다. 왜 하필 level 5~8까지의 소용돌이를 표시했냐면, 목표 숫자들이 포함된 모든 숫자들은 모두 level이 5부터 8까지의 소용돌이 위 숫자들 중 일부로 이루어져있기 때문입니다.
자, 이제 문제를 조금 더 간단히 정리해볼 수 있습니다. (1) 목표로 하는 숫자들이 level 몇부터 몇까지의 소용돌이만 순회하면 되는지를 알아내고, (2) 각 level의 소용돌이의 오른쪽 아래 꼭짓점에 위치한 숫자(2번 규칙으로 쉽게 구할 수 있었죠.)에서 시작하여 시계방향으로 숫자와 그 좌표를 순회하면서 입력받은 범위 내에 좌표가 속하면 그 숫자를 추가합니다. 시계방향으로 순회한다면 순회할 때마다 숫자는 1씩 줄어듭니다. 그리고, (3) 예쁘게 출력하기만 하면 됩니다.
(1) 목표로 하는 숫자들이 level 몇부터 몇까지의 소용돌이만 순회하면 되는지를 알아내고,
입력 받은 영역의 가장 바깥쪽에 위치한 숫자가 몇 level의 소용돌이인지만 알면됩니다. 최대 level의 소용돌이는 입력받은 r1, c1, r2, c2 중, 절댓값의 최댓값입니다. 그 이유는, 이 최댓값이 목표 영역의 각 테두리가 중심으로 부터 얼마나 떨어져 있는지를 보여주기 때문이죠. 그리고 문제에서 r2 - r1의 최댓값은 49이고, c2 - c1의 최댓값은 4이기 때문에 소용돌이 level의 범위는 50을 넘을 수 없습니다. (이 부분은 천천히 생각해보시면 알 수 있어요!) 따라서, 최대 level - 50 부터 최대 level 의 소용돌이 까지만 순회하면 답을 수할 수 있습니다.
(2) 각 level의 소용돌이의 오른쪽 아래 꼭짓점에 위치한 숫자(2번 규칙으로 쉽게 구할 수 있었죠.)에서 시작하여 시계방향으로 숫자와 그 좌표를 순회하면서 입력받은 범위 내에 좌표가 속하면 그 숫자를 추가합니다.
이 때, (r2 - r1 + 1) * (c2 - c1 + 1) 크기의 배열에 먼저 모두 0으로 초기화 시켜 놓고 (해당 숫자의 행 번호 - r1, 해당 숫자의 열 번호 - c1) 위치에 숫자를 넣으면 됩니다. 위의 그림처럼 -8 5 -5 7 을 입력 받은 뒤, 4 * 3 배열을 먼저 만들고 숫자 244의 위치를 볼 때, 이 배열의 (0, 0) 에 위치한다는 것을 보면 이해가 쉽습니다.
(3) 예쁘게 출력하기만 하면 됩니다.
예쁘게 출력하기 위해서는 python의 str.format() 함수를 사용하면 되는데요, 중요한 점은 답에 속한 숫자들의 최대 길이가 몇인지를 아는 것이 중요합니다. 영역에 속한 숫자를 추가할 때마다 최대 길이를 갱신하여 해결했습니다. 그 뒤,
print_format = "{0:>" + str(max_length+1) + "}"
print_format.format(숫자)
이렇게 포맷을 만들어 숫자를 넣고 한 행마다 이어 붙여서 출력하면 됩니다. (출력이 어려우시면 코드의 밑부분만 살짝 보세요 ㅎㅎ)
설명이 참... 애매하게 어렵네요. 과정이 많아서 그런 것 같아요. 아래의 코드로 성공했습니다.
import sys
import time
r1, c1, r2, c2 = map(int, sys.stdin.readline().split())
four_edges = [(r1, c1), (r2, c1), (r1, c2), (r2, c2)]
max_level = max(abs(r1), abs(r2), abs(c1), abs(c2))
# min_level = min(abs(r1), abs(r2))
if r1 * r2 < 0: min_level = 0
result = [[0 for _ in range(c2 - c1 + 1)] for _ in range(r2 - r1 + 1)]
max_length = 0
for level in range(max_level-50, max_level+1):
coord = [level, level]
value = (2 * level + 1) ** 2
if level == 0:
if r1 <= coord[0] <= r2 and c1 <= coord[1] <= c2:
result[coord[0]-r1][coord[1]-c1] = value
continue
# 시작 지점에서 왼쪽으로 이동
for i1 in range(level * 2):
if r1 <= coord[0] <= r2 and c1 <= coord[1] <= c2:
result[coord[0]-r1][coord[1]-c1] = value
# 저장된 값들 중, 가장 긴 길이를 가진 숫자의 길이를 계속해서 갱신
if len(str(value)) > max_length: max_length = len(str(value))
coord[1] -= 1
value -= 1
# 그 다음 위쪽으로 이동
for i2 in range(level * 2):
if r1 <= coord[0] <= r2 and c1 <= coord[1] <= c2:
result[coord[0]-r1][coord[1]-c1] = value
# 저장된 값들 중, 가장 긴 길이를 가진 숫자의 길이를 계속해서 갱신
if len(str(value)) > max_length: max_length = len(str(value))
coord[0] -= 1
value -= 1
# 그 다음 오른쪽으로 이동
for i3 in range(level * 2):
if r1 <= coord[0] <= r2 and c1 <= coord[1] <= c2:
result[coord[0]-r1][coord[1]-c1] = value
# 저장된 값들 중, 가장 긴 길이를 가진 숫자의 길이를 계속해서 갱신
if len(str(value)) > max_length: max_length = len(str(value))
coord[1] += 1
value -= 1
# 그 다음 아래쪽으로 이동
for i4 in range(level * 2):
if r1 <= coord[0] <= r2 and c1 <= coord[1] <= c2:
result[coord[0]-r1][coord[1]-c1] = value
# 저장된 값들 중, 가장 긴 길이를 가진 숫자의 길이를 계속해서 갱신
if len(str(value)) > max_length: max_length = len(str(value))
coord[0] += 1
value -= 1
print_format = "{0:>" + str(max_length+1) + "}"
for row in result:
row_print = ""
for val in row:
row_print += print_format.format(str(val))
if row_print[0] == " ": sys.stdout.write(row_print[1:] + "\n")
else: sys.stdout.write(row_print + "\n")
'Python > 백준 알고리즘' 카테고리의 다른 글
| [백준 알고리즘: python 3] #1912 - 연속합 (DP 스터디) (0) | 2020.03.02 |
|---|---|
| [백준 알고리즘: python 3] #1024 - 수열의 합 (0) | 2020.03.01 |
| [백준 알고리즘: python 3] #1021 - 회전하는 큐 (0) | 2020.01.17 |
| [백준 알고리즘: python 3] #1019 - 책 페이지 (3) | 2020.01.16 |
| [백준 알고리즘: python 3] #1018 - 체스판 다시 칠하기 (0) | 2020.01.15 |
