BOJ - 원판 돌리기 17822번 (python)

❓ 문제 - 백준 원판 돌리기 17822번 - python 풀이법

 

출처 

(https://www.acmicpc.net/problem/17822)

17822번: 원판 돌리기

 

 

 

📝 문제해결법

1. 이 문제는 구현+BFS로 풀었다.

• 문제의 정답은 해당 xi의 배수에 해당하는 원판을 T번 돌린 후 원판에 들어있는 숫자를 더해서 출력해야한다.
• 따라서 돌리려는 원판의 x, d, k를 입력받고 x 의 배수만큼 원판을 돌리는데 rotate() 함수를 사용한다.
• 원판을 돌리는 방법은 queue 를 이용하는데 시계방향으로 k배 만큼 돌리면 rotate(k), 반시계방향 만큼 k배 돌리려면 rotate(-k)로 구현한다.
• 원판을 돌린 후 solve() 함수를 사용하여 모든 판에 대해 인접한 경우에 원판 숫자를 제거하는데, BFS를 돌려서 제거한다.
• solve() 함수를 통해 몇 개의 숫자가 인접하여 제거되었는지 count 갯수가 반환되는데 모든 행과 열에 대해 BFS를 돌려서 인접한 숫자를 제거하는데 인접한 숫자가 하나도 없으면, change_avg() 함수로 원판의 평균값에 해당하는 숫자를 기준으로 원판의 숫자들을 변경한다.
• solve() : BFS로 구현하여 인접한 곳에 숫자가 같은지 파악해서 만약 숫자가 같다면 원판에 숫자를 제거(0으로 변경) 해준다. i번째 원판에는 즉, 0번 열과 m-1 열은 이어져 있으므로 인접 4방향을 살필 때, 값을 잘 변경해줘서 모든 원판에 인접한 곳을 방문할 수 있도록 한다.
• change_avg() : 처음 모든 제거된 숫자(0)을 제외한 나머지 숫자의 갯수와 그 숫자들의 합을 계산한 후, 만약 모든 숫자가 0이라면 평균을 계산하지 않게 리턴해주고, 평균을 계산했다면 모든 원판에 들어있는 숫자들에 값과 비교해서 평균 값보다 크다면 -1, 평균값보다 작다면 +1 해준다. (평균값과 같을 땐, 값의 변화가 없음)
• 다음 원판을 돌릴 때, 한번 원판의 숫자들이 모두 다 제거 되었는지 확인하고 만약 모든 원판의 숫자가 0이 되었다면 원판 돌리기를 중단하고 정답을 출력한다.

2. 문제 풀면서 느낀점

• 문제를 잘 읽자 ^^... 해당 원판의 배수만큼 회전하라는 것과, 평균비교 해서 값 변경할 때 평균과 같을 때도 잘 신경써야 한다.

 

 

💻 소스코드

from collections import deque

n, m, t = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
# 동 - 서 - 남 - 북
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def rotate(x, d, k):
    q = deque()
    q.extend(graph[x])
    if d == 0:
        q.rotate(k)
    else:
        q.rotate(-k)
    graph[x] = list(q)


def change_avg():
    avg_count = 0
    all_sum = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] != 0:
                avg_count += 1
                all_sum += graph[i][j]
    if avg_count == 0:
        return False
    avg = all_sum / avg_count
    for i in range(n):
        for j in range(m):
            if graph[i][j] != 0:
                if graph[i][j] > avg:
                    graph[i][j] -= 1
                elif graph[i][j] < avg:
                    graph[i][j] += 1
    return True

def solve(x, y):
    q = deque()
    q.append((x, y))
    visited[x][y] = True
    value = graph[x][y]
    graph[x][y] = 0
    count = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 > ny or ny >= m:
                if y == 0:
                    ny = m-1
                elif y == m-1:
                    ny = 0
            if 0 <= nx < n and 0 <= ny < m:
                if not visited[nx][ny]:
                    if graph[nx][ny] == value:
                        count += 1
                        graph[nx][ny] = 0
                        visited[nx][ny] = True
                        q.append((nx, ny))
    if count == 0:
        graph[x][y] = value
    return count


for _ in range(t):
    x, d, k = map(int, input().split())
    check_sum = 0
    for i in range(n):
        check_sum += sum(graph[i])
        if (i+1) % x == 0:
            rotate(i, d, k)
    if check_sum == 0:
        break
    else:
        visited = [[False] * m for _ in range(n)]
        count = 0
        for i in range(n):
            for j in range(m):
                if not visited[i][j] and graph[i][j] != 0:
                    count += solve(i, j)
        if count == 0:
            change_avg()

answer = 0
for i in range(n):
    answer += sum(graph[i])

print(answer)