[백준 17822번] 원판 돌리기
이 문제는 BFS와 시뮬레이션 문제이다.
갈수록 삼성 SW 역량 테스트의 문제가 점점 더 구현에 까다로운 조건을 추가하기 시작하는 게 느껴진다.
먼저, 문제를 풀기 위해 원판의 숫자를 어떻게 표현할 것인지에 대해서 생각해보아야 한다.
문제에서 주어진 원판을 행렬로 표현하면 다음과 같다.
이제 원판을 행렬로 나타냈으니, 원판을 회전시키는 함수를 작성한다.
i번째의 원판을 회전시킬 때, i의 배수인 원판 모두 회전을 시켜야 한다.
이 부분에 대한 구현은 13~27번째 줄에 다음과 같이 구현되어 있다.
def rotate(_x, _d, _k):
# rotate counter-clockwise
if _d:
# for all disks which is multiple of x
for i in range(_x, n + 1, _x):
temp = deque(disk[i][1:])
temp.rotate(-(_k % m))
disk[i][1:] = temp
# rotate clockwise
else:
# for all disks which is multiple of x
for i in range(_x, n + 1, _x):
temp = deque(disk[i][1:])
temp.rotate(_k % m)
disk[i][1:] = temp
deque 자료형은 built-in 함수로 rotate 함수를 제공한다.
그래서 나는 주어진 원판의 행렬에서 각 행을 deque 자료형으로 바꾸고, 회전시켜주었다.
지금 생각해보니 list형이 아니라 deque형으로 원판의 숫자를 읽어도 될 것 같다.
문제를 해결하기 위한 기본적인 함수를 작성했으니, 이제 문제에서 주어진대로 문제를 풀면 된다.
문제를 푼 로직은 다음과 같다.
- 주어진 횟수만큼 문제에서 언급한 대로 원판을 회전시킨다. (31~33번째 줄)
- 원판을 회전시킨 후, 모든 칸에 대한 BFS를 통해 인접하면서 같은 숫자를 찾는다. (35~63번째 줄, 70번째 줄)
- BFS를 통해 찾은 인접한 숫자 중 같은 숫자가 있다면 그 숫자들을 원판에서 지운다. (65~68번째 줄)
- BFS를 통해 찾은 인접한 숫자 중 같은 숫자가 없다면, 원판에 적힌 숫자들의 평균을 구하고, 평균보다 큰 수에서 1을 빼고 평균보다 작은 수에는 1을 더한다. (72~90번째 줄)
이 문제가 까다로운 점은 숨은 조건이 있다는 것이다.
먼저 첫 번째 숨은 조건은 2번에 있다.
우리는 먼저 원판을 행렬로 표현했다. 하지만 여기서 주의할 점은, 원판에서 인접한 숫자는 행렬의 양쪽 끝도 인접해있다는 것이다.
다음의 그림을 보면 이해하기 쉽다.
따라서 BFS를 통해 인접하면서 같은 숫자를 찾기 위해서는 이 숨은 조건 또한 포함해야 한다.
이 숨은 조건은 56~63번째 줄에 구현되어 있다.
사실 이 조건은 이미 문제에 제시되어 있지만, 간과하기 쉬운 조건이다.
두 번째 숨은 조건은 원판에 적힌 숫자들의 평균을 구할 때이다.
백준의 예제 입력에서는 찾을 수 없는 조건이지만, 19년 하반기 삼성전자 SW 역량 테스트의 예제 입력에서 찾을 수 있는 조건이었다.
원판에서 평균을 구할 때 0이 아닌 숫자를 찾아야 하는데, 이때 0이 아닌 숫자가 없다면 division by zero 에러가 발생한다.
따라서 이 부분에 대해서도 조건 검사를 해주어야 한다.
이 숨은 조건은 80~82번째 줄에 구현되어 있다.
import sys
from collections import deque
# initialize
n, m, t = map(int, sys.stdin.readline().split())
disk = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for r in range(1, n + 1):
line = list(map(int, sys.stdin.readline().split()))
for c in range(1, m + 1):
disk[r][c] = line[c - 1]
def rotate(_x, _d, _k):
# rotate counter-clockwise
if _d:
# for all disks which is multiple of x
for i in range(_x, n + 1, _x):
temp = deque(disk[i][1:])
temp.rotate(-(_k % m))
disk[i][1:] = temp
# rotate clockwise
else:
# for all disks which is multiple of x
for i in range(_x, n + 1, _x):
temp = deque(disk[i][1:])
temp.rotate(_k % m)
disk[i][1:] = temp
directions = ((0, 1), (1, 0), (0, -1), (-1, 0))
for _ in range(t):
x, d, k = map(int, sys.stdin.readline().split())
rotate(x, d, k)
found = False
total_visited = set()
for r in range(1, n + 1):
for c in range(1, m + 1):
if (r, c) not in total_visited:
q = deque([(r, c)])
visited = set([(r, c)])
# BFS
while q:
cur_r, cur_c = q.pop()
# for 4 adjacent numbers
for dr, dc in directions:
next_r = cur_r + dr
next_c = cur_c + dc
if 0 < next_r <= n and 0 < next_c <= m and (next_r, next_c) not in visited:
# if it's the same number
if disk[next_r][next_c] and disk[cur_r][cur_c] == disk[next_r][next_c]:
q.appendleft((next_r, next_c))
visited.add((next_r, next_c))
# hidden condition for circular disk
if disk[cur_r][cur_c]:
if (cur_r, m) not in visited and cur_c == 1 and disk[cur_r][cur_c] == disk[cur_r][m]:
q.appendleft((cur_r, m))
visited.add((cur_r, m))
elif (cur_r, 1) not in visited and cur_c == m and disk[cur_r][cur_c] == disk[cur_r][1]:
q.appendleft((cur_r, 1))
visited.add((cur_r, 1))
if len(visited) > 1:
for vr, vc in visited:
disk[vr][vc] = 0
found = True
total_visited |= visited
if not found:
count, average = 0, 0
for i in range(1, n + 1):
for j in range(1, m + 1):
if disk[i][j]:
count += 1
average += disk[i][j]
# filter divide by zero
if count:
average /= count
for i in range(1, n + 1):
for j in range(1, m + 1):
if disk[i][j]:
if disk[i][j] > average:
disk[i][j] -= 1
elif disk[i][j] < average:
disk[i][j] += 1
print(sum(map(sum, disk)))