algorithm/Implementation
[백준17822/골드2] 원판 돌리기 - Python
ayeongjin
2025. 3. 30. 00:17
https://www.acmicpc.net/problem/17822
매 T 마다 반복되는 동작은
1. 원판 회전
2-1. 인접한 값 중 서로 같은 값이 있으면 그 값들 삭제
2-2. 인접하면서 같은 수가 없는 경우에는 원판 수의 합보다 작은 수는 += 1, 큰 수는 -= 1
그래서 세가지 함수를 만들었다.
1. 원판 회전
def turn(x, d, k): # x의 배수인 원판을 d(0: 시계, 1: 반시계) 방향으로 k칸 회전
for i in range(x, N+1, x):
if d == 0: # 시계 방향
circles[i-1] = circles[i-1][-k:] + circles[i-1][:-k]
else: # 반시계 방향
circles[i-1] = circles[i-1][k:] + circles[i-1][:k]
2. 원판 인접한 숫자가 같으면 해당 연결 숫자들 삭제
(각 원판 숫자를 순회 -> 인접한 숫자가 같은 숫자일시 bfs 실행)
def number_delete():
deleted = False
visited = [[False] * M for _ in range(N)]
q = deque([])
for i in range(N):
for j in range(M):
if not visited[i][j] and circles[i][j] != 0:
visited[i][j] = True
q.append((circles[i][j], i, j))
while q:
num, ci, cj = q.popleft()
for di, dj in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
ni, nj = ci + di, cj + dj
if not (0 <= nj < M):
# 원형 배열 체크
nj = (M-1 if nj < 0 else 0 if nj > M-1 else nj)
if 0 <= ni < N and 0 <= nj < M and not visited[ni][nj] and circles[ni][nj] == num:
deleted = True
visited[ni][nj] = True
circles[i][j] = 0
circles[ni][nj] = 0
q.append((num, ni, nj))
return deleted
3. 원판 평균값 기준으로 숫자 조정
def number_control():
total = sum(sum(circles[i]) for i in range(N))
cnt = sum(1 for i in range(N) for j in range(M) if circles[i][j] > 0)
if cnt == 0:
return
average = total / cnt # 0을 제외한 평균값
for i in range(N):
for j in range(M):
if circles[i][j] > 0:
if circles[i][j] > average:
circles[i][j] -= 1
elif circles[i][j] < average:
circles[i][j] += 1
마지막으로 T번 원판 회전 반복하면서 조건에 맞는 숫자 삭제 또는 숫자 조정 실행
for _ in range(T):
# 1. 원판 회전
x, d, k = map(int, input().split())
turn(x, d, k)
# 2-1. 인접하면서 같은 수가 있는 경우에 그 수 삭제
if number_delete():
continue
# 2-2. 인접하면서 같은 수가 없는 경우에 원판 수의 합보다 작은 수는 += 1 큰 수는 -= 1
number_control()
print(sum(sum(line) for line in circles))
# 성공 코드 1
# 인접칸만 확인하며 삭제
# python 32544 KB 120 ms
N, M, T = map(int, input().split())
circles = [list(map(int, input().split())) for _ in range(N)]
def turn(x, d, k): # x의 배수인 원판을 d(0: 시계, 1: 반시계) 방향으로 k칸 회전
for i in range(x, N+1, x):
if d == 0: # 시계 방향
circles[i-1] = circles[i-1][-k:] + circles[i-1][:-k]
else: # 반시계 방향
circles[i-1] = circles[i-1][k:] + circles[i-1][:k]
def number_delete():
deleted = False
to_delete = set()
for i in range(N):
for j in range(M):
if circles[i][j] == 0:
continue
num = circles[i][j]
for di, dj in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
ni, nj = i + di, (j + dj) % M
if 0 <= ni < N and circles[ni][nj] == num:
to_delete.add((i, j))
to_delete.add((ni, nj))
if to_delete:
deleted = True
for i, j in to_delete:
circles[i][j] = 0
return deleted
def number_control():
total = sum(sum(circles[i]) for i in range(N))
cnt = sum(1 for i in range(N) for j in range(M) if circles[i][j] > 0)
if cnt == 0:
return
average = total / cnt # 0을 제외한 평균값
for i in range(N):
for j in range(M):
if circles[i][j] > 0:
if circles[i][j] > average:
circles[i][j] -= 1
elif circles[i][j] < average:
circles[i][j] += 1
for _ in range(T):
# 1. 원판 회전
x, d, k = map(int, input().split())
turn(x, d, k)
# 2-1. 인접하면서 같은 수가 있는 경우에 그 수 삭제
if number_delete():
continue
# 2-2. 인접하면서 같은 수가 없는 경우에 원판 수의 합보다 작은 수는 += 1 큰 수는 -= 1
number_control()
print(sum(sum(line) for line in circles))
이렇게 하고 보니 인접하면서 같은 숫자 삭제를 굳이 bfs로 순회하면서 찾을 필요가 없었다.
내 함수는 어차피 모든 원판을 순회하면서 인접한 수를 찾고 있었기 때문에~..
그래서 인접한 숫자를 저장할 집합을 만들고 각 칸을 순회하며 인접하면서 같은 숫자는 따로 모아줬다.
그리고 마지막에 한번에 그 숫자들을 삭제하는 방식으로 리팩토링했다.
2. 원판 인접한 숫자가 같으면 해당 연결 숫자들 삭제
(각 원판 숫자를 순회 -> 인접한 숫자가 같은 숫자일시 따로 집합에 모으기 -> 마지막에 전부 0으로 숫자 삭제)
def number_delete():
deleted = False
to_delete = set()
for i in range(N):
for j in range(M):
if circles[i][j] == 0:
continue
num = circles[i][j]
for di, dj in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
ni, nj = i + di, (j + dj) % M
if 0 <= ni < N and circles[ni][nj] == num:
to_delete.add((i, j))
to_delete.add((ni, nj))
if to_delete:
deleted = True
for i, j in to_delete:
circles[i][j] = 0
return deleted
# 성공 코드 2
# bfs로 인접하고 같은 숫자 삭제
# python 35092 KB 176 ms
from collections import deque
N, M, T = map(int, input().split())
circles = [list(map(int, input().split())) for _ in range(N)]
def turn(x, d, k): # x의 배수인 원판을 d(0: 시계, 1: 반시계) 방향으로 k칸 회전
for i in range(x, N+1, x):
if d == 0: # 시계 방향
circles[i-1] = circles[i-1][-k:] + circles[i-1][:-k]
else: # 반시계 방향
circles[i-1] = circles[i-1][k:] + circles[i-1][:k]
def number_delete():
deleted = False
visited = [[False] * M for _ in range(N)]
q = deque([])
for i in range(N):
for j in range(M):
if not visited[i][j] and circles[i][j] != 0:
visited[i][j] = True
q.append((circles[i][j], i, j))
while q:
num, ci, cj = q.popleft()
for di, dj in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
ni, nj = ci + di, cj + dj
if not (0 <= nj < M):
nj = (M-1 if nj < 0 else 0 if nj > M-1 else nj)
if 0 <= ni < N and 0 <= nj < M and not visited[ni][nj] and circles[ni][nj] == num:
deleted = True
visited[ni][nj] = True
circles[i][j] = 0
circles[ni][nj] = 0
q.append((num, ni, nj))
return deleted
def number_control():
total = sum(sum(circles[i]) for i in range(N))
cnt = sum(1 for i in range(N) for j in range(M) if circles[i][j] > 0)
if cnt == 0:
return
average = total / cnt # 0을 제외한 평균값
for i in range(N):
for j in range(M):
if circles[i][j] > 0:
if circles[i][j] > average:
circles[i][j] -= 1
elif circles[i][j] < average:
circles[i][j] += 1
for _ in range(T):
# 1. 원판 회전
x, d, k = map(int, input().split())
turn(x, d, k)
# 2-1. 인접하면서 같은 수가 있는 경우에 그 수 삭제
if number_delete():
continue
# 2-2. 인접하면서 같은 수가 없는 경우에 원판 수의 합보다 작은 수는 += 1 큰 수는 -= 1
number_control()
print(sum(sum(line) for line in circles))
cf) 원판 회전 메서드 .rotate()
원판 회전을 하면서
1. 슬라이싱으로 새로운 배열 만들기
2. popleft(), push()로 k번 반복해서 재배치하기
두가지를 생각했는데, heapq 모듈에서 .heappoppush() 메서드같은게 deque에도 있지 않을까 해서 찾아봤다.
deque에는 .poppush()같은 메서드는 없고, .rorate()로 비슷한 효과를 낼 수 있었다.
1. 원판 회전
(.rotate() 사용)
def turn(x, d, k): # x의 배수인 원판을 d(0: 시계, 1: 반시계) 방향으로 k칸 회전
for i in range(x, N+1, x):
if d == 0: # 시계 방향
circles[i-1].rotate(k)
else: # 반시계 방향
circles[i-1].rotate(-k)
.rorate() 메서드가 더 빠를거라고 생각했는데, 실제 정답 제출에서는 슬라이싱으로 새로운 배열로 할당하는 게 더 빨랐다.
M이 50밖에 안돼서 내부 연산이 오래걸리는거같다.
그래서 최종 제출에는 사용하지 않았다.