[ 백준 17822 ] 원판 돌리기 - Python

문제 보기

DFS, 구현, 시뮬레이션 문제이다.

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구하면 된다.

 

원판 돌리기에서 필요한 연산은 2가지이다.

1. 원판 회전

2. 인접하면서 같은 수를 지우기

 

원판 회전은 시계 방향, 반시계 방향으로 나눠서 구현하였다.

시계 방향은 array[i] = [array[i][-1]] + array[i][:-1]로 구현하였다. 마지막 값을 제일 앞으로 옮겼다.

반시계 방향은 array[i] = array[i][1:] + [array[i][0]]로 구현하였다. 첫 번째 값을 마지막 위치로 옮겼다.

 

인접하면서 같은 수 지우는 연산은 dfs로 구현하였다,

현재 위치의 상, 하, 좌, 우에 현재 위치에 있는 값이랑 같은 값이 있으면 계속해서 탐색하도록 하였다.

예를 들어 현재 위치의 오른쪽에 같은 값이 있으면 오른쪽값에서도 다시 상, 하, 좌, 우를 탐색하여 같은 값이 있는지 파악하였다.

 

참고로 원판 돌리기 문제는 sys.setrecursionlimit로 재귀 깊이를 넓혀주지 않으면 런타임 에러가 발생한다.

코드

import sys
sys.setrecursionlimit(10**9)
flag = False


def dfs(array, r, c, value):
    global flag

    # 오른쪽
    if c + 1 < m and array[r][c + 1] == value:
        flag = True
        array[r][c] = "x"
        array[r][c + 1] = "x"
        dfs(array, r, c + 1, value)
    elif c + 1 == m and array[r][0] == value:
        flag = True
        array[r][c] = "x"
        array[r][0] = "x"
        dfs(array, r, 0, value)

    # 왼쪽
    if c - 1 >= 0 and array[r][c - 1] == value:
        flag = True
        array[r][c] = "x"
        array[r][c - 1] = "x"
        dfs(array, r, c - 1, value)
    elif c - 1 == -1 and array[r][m - 1] == value:
        flag = True
        array[r][c] = "x"
        array[r][m - 1] = "x"
        dfs(array, r, m - 1, value)

    # 아래
    if r - 1 >= 0 and array[r - 1][c] == value:
        flag = True
        array[r][c] = "x"
        array[r - 1][c] = "x"
        dfs(array, r - 1, c, value)

    # 위
    if r + 1 < n and array[r + 1][c] == value:
        flag = True
        array[r][c] = "x"
        array[r + 1][c] = "x"
        dfs(array, r + 1, c, value)


def solve(array, test, n, m):
    global flag

    # 회전
    if test[1] == 0:  # 시계 방향
        for i in range(test[0] - 1, n, test[0]):
            for _ in range(test[2]):
                array[i] = [array[i][-1]] + array[i][:-1]
    else:  # 반시계 방향
        for i in range(test[0] - 1, n, test[0]):
            for _ in range(test[2]):
                array[i] = array[i][1:] + [array[i][0]]

    # 인접하면서 같은 수를 모두 지운다.
    flag = False
    for i in range(n):
        for j in range(m):
            if array[i][j] != "x":
                dfs(array, i, j, array[i][j])

    if not flag:  # 인접한 수가 없었던 경우
        total = 0
        cnt = 0
        for i in range(n):
            for j in range(m):
                if array[i][j] != "x":
                    total += array[i][j]
                    cnt += 1

        if cnt <= 1:
            return
        else:
            average = total / cnt
            for i in range(n):
                for j in range(m):
                    if array[i][j] != "x":
                        if array[i][j] > average:
                            array[i][j] -= 1
                        elif array[i][j] < average:
                            array[i][j] += 1


if __name__ == "__main__":
    n, m, t = map(int, input().split())  # 원판의 개수, 각 원판이 가지는 숫자의 개수, 명령 개수
    array = [list(map(int, input().split())) for _ in range(n)]

    task = [list(map(int, input().split())) for _ in range(t)]
    for i in range(t):
        solve(array, task[i], n, m)

    # 출력
    answer = 0
    for i in range(n):
        for j in range(m):
            if array[i][j] != "x":
                answer += array[i][j]
    print(answer)