[백준]1913 달팽이 - 실버3
[오늘의 문제]
https://www.acmicpc.net/problem/1913
[오늘의 학습 키워드]
- 구현
1. 문제설명
홀수인 자연수 N이 주어지면, 다음 그림처럼 1부터 N^2 까지의 자연수를 달팽이 모양으로 N x N 의 표에 채우고 특정 수를 찾는 문제입니다.
[제한사항]
- 시간 제한 2초
- 메모리 제한 128MB
- 3 ≤ N ≤ 999
2. 접근방식
우선 문제의 제한사항부터 보면 2차원 배열을 달팽이 모양으로 채우려면 결국 전체탐색인 N X N 만큼의 시간이 걸릴 것입니다.
그러면 최대 999 X 999가 발생하는데 이는 998,001 으로 1초에 최대 100만번 동작을 실행하는 파이썬은 무리없이 수행가능한 시간입니다.
또 시간 제한이 2초 이므로 시간은 신경쓰지 않고 구현하면 될 것 같습니다.
구현의 목표는 중심에서 부터 왼쪽, 위, 오른쪽, 아래 순서로 달팽이를 채워나가야 합니다.
채워나갈때도 1부터 N^2 까지 채우니까 0, 0 에서 부터 접근하기 쉽게 N^2 부터 채우면서 1씩 감소해 채워주면 될 것 같습니다.
0, 0 을 N ^ 2 으로 채우고 중심이 1이 되려면 아래, 오른쪽, 위, 왼쪽 순서로 돌아가면서 채워주면 중심이 1이 됩니다.
그럼 이 각각을 구현하면 되는데
저는 구현할 때 일련의 동작을 시행하면서 print로 확인하며 구현을 실시합니다.
결국 인덱싱 문제이므로 범위를 벗어나거나, 변수를 중복으로 사용하는 경우를 고려하여 문제를 해결해 주었습니다.
3. 코드
N = int(input()) # 자연수
find_num = int(input()) # 찾고자 하는 숫자
snail = [[0] * N for _ in range(N)] # 배열을 저장할 2차원 배열
temp = N ** 2 # 자연수를 1씩 감소하며 채워나가기
# 특정 위치의 접근을 쉽게 하기 위해 row, column을 선언하여 사용
row = N-1
column = 0
# 중첩 반복문을 이용하면 최대 999 x 999로 1초 이내에 시행 가능함
for num in range(N):
# 왼쪽 세로 채우기
for i in range(num, N):
if snail[i][num] != 0:
continue
snail[i][column] = temp
temp -= 1
# 바닥줄 채우기
for j in range(num, N):
if snail[row][j] != 0:
continue
snail[row][j] = temp
temp -= 1
# 오른쪽 세로 올라가며 채우기
for i in range(N-1, num, -1):
if snail[i][row] != 0:
continue
snail[i][row] = temp
temp -= 1
# 가장 위부터 채우기
for j in range(N-1, num, -1):
if snail[column][j] != 0:
continue
snail[column][j] = temp
temp -= 1
# 위치 맞춰주기
row -= 1
column += 1
# 정답 출력
for i in range(N):
for j in range(N):
if snail[i][j] == find_num:
for s in snail:
print(*s)
print(i+1, j+1)
exit()[코드설명]
column = 0
# 중첩 반복문을 이용하면 최대 999 x 999로 1초 이내에 시행 가능함
for num in range(N):
# 왼쪽 세로 채우기
for i in range(num, N):
if snail[i][num] != 0:
continue
snail[i][column] = temp
temp -= 1
column += 1
입력을 받고 2차원 배열을 생성하였으니 우선 0, 0에서 부터 0, N-1 까지 세로로 채워주는데
이때, 입력받는 num에 따라 세로로 채워주는 위치가 변하게 됩니다.
이 코드만 이용해서 snail을 채워보면 다음과 같이 채워집니다.
[49, 0, 0, 0, 0, 0, 0]
[48, 42, 0, 0, 0, 0, 0]
[47, 41, 36, 0, 0, 0, 0]
[46, 40, 35, 31, 0, 0, 0]
[45, 39, 34, 30, 27, 0, 0]
[44, 38, 33, 29, 26, 24, 0]
[43, 37, 32, 28, 25, 23, 22]
column이 1씩 계속 증가하고 i 역시 num 부터 N까지 채워나가니 num이 증가하며 0, 1, 2, 3, 4 에 맞춰 한 칸씩 아래에서 채워줍니다.
이렇게 채워야 쓸데없는 동작을 최소화 하며 우리가 채우려는 목표로 채울 수 있습니다.
올바르게 세로로 내려가며 채웠으니 바닥줄을 채워줘야 합니다.
row = N - 1
# 바닥줄 채우기
for j in range(num, N):
if snail[row][j] != 0:
continue
snail[row][j] = temp
temp -= 1
row -= 1
바닥줄은 바닥에서부터 위로 올라오며 한 칸씩 채워줘야 합니다.
이 코드만 이용해서 snail을 채워보면 다음과 같습니다.
[0, 0, 0, 0, 0, 0, 22]
[0, 0, 0, 0, 0, 24, 23]
[0, 0, 0, 0, 27, 26, 25]
[0, 0, 0, 31, 30, 29, 28]
[0, 0, 36, 35, 34, 33, 32]
[0, 42, 41, 40, 39, 38, 37]
[49, 48, 47, 46, 45, 44, 43]
동일하게 세로로 채우는 과정을 반복하는데 한 칸씩 안쪽으로 들어가며 채워주죠
다음은 위로 올라가는 코드 입니다.
# 오른쪽 세로 올라가며 채우기
for i in range(N-1, num, -1):
if snail[i][row] != 0:
continue
snail[i][row] = temp
temp -= 1
동일하게 row로 접근해 주었고 row가 1씩 감소하기 때문에 가장 오른쪽에서 부터 안쪽으로 이동하겠죠
그럼 i는 바닥에서 위로 올라가는 코드만 짜면 되고 도착 위치는 num까지 도착하면 나머지는 채워져 있겠죠
마지막으로 상단을 채우는 코드 입니다.
# 가장 위 채우기
for j in range(N-1, num, -1):
if snail[column][j] != 0:
continue
snail[column][j] = temp
temp -= 1
상단은 위에서 아래로 이동하며 뒤에서 앞으로 채워줘야 합니다.
그럼 j는 뒤에서 앞으로 이동하고
column은 0에서 1씩 증가하며 채우면 되겟죠
이를 종합하였고 정답을 출력할 때 전체 탐색을 실시해 입력받은 찾으려는 숫자를 찾은 경우 해당 위치와 배열을 출력해 주었습니다.
4. 결과
[회고]
이번 문제는 해결하는 과정에서 예전 swea에서 해결했던 달팽이 문제와 유사한 문제 였습니다.
그때에도 이러한 방식으로 문제를 해결하였는데 하나씩 조건에 맞춰 구현하고 합쳐서 출력하였을 때 제대로 동작하는 것을 보며 어렵지 않게 해결할 수 있었습니다.
이번 문제를 해결하는 핵심은 반복문을 사용하며 특정 row 와 column에 접근하는 것이었습니다.
약간 투포인터 느낌도 들었고, 구현을 하나씩 하며 재사용가능한 것을 찾아가며 구현하니 재밌고 쉽게 해결할 수 있었습니다.
다음에도 비슷한 구현 문제를 해결해 보겠습니다.