17822. 원판 돌리기 문제 바로가기
해결 방법
크게 회전하는 부분과 인접한 숫자가 있는지 확인하는 것이 주요 과정이라고 생각했습니다.
각 두가지 부분에 대한 구현을 설명하겠습니다.
회전하기
저는 회전하는 것을 구현하기 위해서 슬라이싱을 사용했습니다.
k 번 만큼 회전하는 것이기에
반시계 방향일 때는 k 부분을 기준으로 순서를 바꿔주면 됩니다.
ex) 1 2 3 4 5 → 반시계 방향으로 2번 회전시키면 3 4 5 1 2
시계 방향일 때는 -k 부분을 기준으로 순서를 바꿔주면 됩니다.
ex) 1 2 3 4 5 → 시계 방향으로 2번 회전시키면 4 5 1 2 3
1 2 3 4
if d == 0: # 시계 방향 circles[xx - 1] = circles[xx - 1][-k:] + circles[xx - 1][:-k] else: # 반시계 방향 circles[xx - 1] = circles[xx - 1][k:] + circles[xx - 1][:k]
인접한 숫자가 있는 지 확인하기
queue를 이용하여서 인접한 부분이 같은 숫자인지 확인하도록 하였습니다. 이때 원판이기에 행부분에서 0번 인덱스와 끝번 인덱스가 연결되어 있다는 점을 해결하기 위해
1
nx = (nx + M) % M
다음과 같이 계산하여 연결되어 있음을 확인했습니다.
구현한 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
from copy import deepcopy
N, M, T = map(int, input().split())
circles = [list(map(int, input().split())) for _ in range(N)]
rotate = [list(map(int, input().split())) for _ in range(T)]
for t in range(T):
# 1. x의 배수인 원판을 d 만큼 k 칸 회전 시키기
x, d, k = rotate[t]
xx = x
while xx <= N:
if d == 0: # 시계 방향
circles[xx - 1] = circles[xx - 1][-k:] + circles[xx - 1][:-k]
else: # 반시계 방향
circles[xx - 1] = circles[xx - 1][k:] + circles[xx - 1][:k]
xx += x
n_circles = [[-1] * M for _ in range(N)]
# 2. 원판의 수가 있는 경우 인접한 수 탐색하기
# 2-1. 인접한 수가 서로 같으면 모두 0으로 지운다.
dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
no_change = True # 인접한 수가 없었는지 기준이 되는 변수
for y in range(N):
for x in range(M):
if circles[y][x] > 0:
q = [[y, x]]
while q:
qy, qx = q.pop(0)
for d in range(4):
ny, nx = qy + dirs[d][0], qx + dirs[d][1]
nx = (nx + M) % M # 원판 => 행의 인덱스 0번이랑 마지막 번이 이어져 있음을 고려
if 0 <= ny < N and circles[y][x] == circles[ny][nx] and n_circles[ny][nx] == -1:
n_circles[y][x] = 0
n_circles[ny][nx] = 0
q.append([ny, nx])
if no_change: no_change = False
if n_circles[y][x] == -1: # 인접하지 않은 수이기에 원래 값 저장하기
n_circles[y][x] = circles[y][x]
elif circles[y][x] == 0: # 지워진 수라는 것을 저장하기
n_circles[y][x] = 0
# 2-2. 원판에 인접한 수가 없는 경우 새로운 값으로 갱신한다.
if no_change:
num_sum = 0
num_cnt = 0
change_list = [] # 원판에 적힌 수의 위치를 저장할 리스트
for y2 in range(N):
for x2 in range(M):
if n_circles[y2][x2] > 0:
num_sum += n_circles[y2][x2]
num_cnt += 1
change_list.append([y2, x2])
if num_cnt != 0: # 조건 필요! (없으면 런타임 에러-ZeroDivisionError 발생)
num_avg = num_sum / num_cnt
for c in change_list: # 평균 기준으로 큰 수는 -1, 작은 수는 +1로 값 변경하기
if n_circles[c[0]][c[1]] > num_avg:
n_circles[c[0]][c[1]] -= 1
elif n_circles[c[0]][c[1]] < num_avg:
n_circles[c[0]][c[1]] += 1
circles = deepcopy(n_circles)
# 최종저긍로 원판에 적힌 수의 합 구하기
final_sum = 0
for i in range(N):
final_sum += sum(circles[i])
print(round(final_sum))