17822번. 원판 돌리기

http://boj.kr/17822 

17822번: 원판 돌리기

 

 

1. 원판을 2차원 배열로 생각해서 같은 원에 있는 숫자들은 같은 행에 속한 숫자들이라고 생각하고, 위아래로 접한 숫자들은 같은 열에 속한 숫자들이라고 생각한다.

행 (펼쳐준다)

열

2. 문제에서 주어진 일련의 과정을 몇가지로 나눈다.

 

1) 기저사례를 확인한다. 원판에 수가 남아있는지 확인해서 남아있으면 더 진행하고, 남아있지 않으면 반복문을 종료한다.

원판에 숫자가 남아있는지 추적하기 위해 N * M = remain이라는 변수를 따로 두었다. 

 

2) 각 행을 회전시킨다. 회전을 쉽게 하기 위해서 각 원판의 자료형을 list가 아닌 deque로 두었다. deque을 시계방향으로 회전하려면 deque.rotate(k), 반시계방향으로 회전하려면 deque.rotate(-k) 하면 된다. 너무 쉽다.

너무 쉬워서 찜찜하면 temp 배열을 하나 새로 만들어서 직접 위치를 계산해서 옮겨주면 된다.

 

3) 2차원 배열을 순환하면서 각 원소마다 인접한 숫자가 있는지 확인하고, 있으면 그 숫자를 지울 것이라는 표시를 담은 erase 배열에 True라고 체크한다.

문제를 처음 풀었을 때는 지문에서 각 행렬마다 어떻게 비교해야되는지 예외 케이스까지 조건을 친절하게 알려줬으므로 그대로 따라서 if-elif 문으로 비교했다. 물론 그래도 된다. 

 

하지만 어떤 문제에서는 이 문제처럼 직접 비교 조건을 알려주지 않고 그냥 인접한 숫자끼리 비교하라고만 할 수도 있다. 그럴 때는 지문에서 알려준 것처럼 i=0일 때, i=N-1일 때, 0 < i < N-1, j=0일 때, j=M-1일때, 0 < j < M-1 일때로 나눠서 코딩하기보다는 BFS나 DFS 탐색 문제처럼 동서남북 방향의 원소와 비교해야 한다고 생각하고 코딩하는 편이 빠를 것 같다. 중첩 if문으로 코딩하면 중복된 코드가 많아져서 자료형이라도 수정해야 될 때 긴 시간을 소모해야 할 수도 있다.

 

나는 미로찾기 문제를 BFS나 DFS로 풀 때처럼 dx와 dy를 미리 선언해주었다. 하지만 동서남북 방향의 네 원소와 모두 비교할 필요는 없고, →방향과 ↓방향의 원소와만 비교해도 된다. 어차피 중복되기 때문이다. 주의해야 할 점이 col은 원형 리스트이므로, col과 아래쪽 방향 next_c를 비교하려고 할 때 next_c가 범위를 벗어나면 0으로 바꿔줘야 한다. 반면 row는 원형 리스트가 아니므로 범위를 벗어나면 무시하면 된다.

 

4) 3번에서 지울 숫자들을 다 표시했으면, 이번에는 그 erase 배열을 순환하면서 True라고 체크된 숫자들을 0으로 지우고, 지웠으면 다시 erase 배열을 반복문에서 사용하기 위해서 False로 돌려놓는다. 5)번을 수행하기 위해서 지운 숫자가 있음을 표시하는 bool 변수 once_erase를 True로 체크한다.

 

5) 지운 숫자가 있음을 표시하는 bool 변수 once_erase가 False면 평균을 구해서 평균보다 작은 숫자는 +1, 큰 숫자는 -1을 해 주었다.

import sys
from collections import deque


def solve():
    remain = N * M
    for x, direct, k in move:  # x=x의 배수인 원판을 회전,direct=시계(0),반시계(1),k=몇칸 회전하는지
        if remain <= 0:  # 남아 있는 숫자가 없으면 반복문을 빠져나온 후 sum을 리턴
            break

        # x의 배수인 원판(행)을 모두 구해서 회전시킨다.
        if direct == 0:  # 시계방향
            for next_x in range(1, N+1):  # next_x = x의 배수인 원판(=행)
                if next_x % x == 0:
                    circle[next_x-1].rotate(k)
        else:  # 반시계방향
            for next_x in range(1, N+1):
                if next_x % x == 0:
                    circle[next_x-1].rotate(-k)

        # 인접한 것이 있는지 찾고, 있으면 지운다
        for row in range(N):
            for col in range(M):
                if circle[row][col]:  # 이미 지운 숫자는 보지 않는다
                    for i in range(2):  # 오른쪽, 아래쪽과 비교
                        next_r, next_c = row + dx[i], col + dy[i]
                        if next_c > M-1:  # col이 맨 끝에 도달했을 때는 next_c를 0으로 설정한다.
                            next_c = 0

                        if next_r < N:  # r은 범위를 벗어나면 그냥 무시한다
                            if circle[next_r][next_c] == circle[row][col]:
                                erase[next_r][next_c], erase[row][col] = True, True

        once_erased = False  # 지운 숫자가 있음을 체크할 bool 변수
        for row in range(N):
            for col in range(M):
                if erase[row][col]:  # 인접한 숫자가 있는 원소 (erase가 True로 체크된 원소)
                    once_erased = True
                    circle[row][col] = 0
                    remain -= 1  # 숫자를 지웠으니 남은 숫자를 의미하는 remain에서 1을 빼준다
                    erase[row][col] = False  # 다음 반복문에서 재사용하기 위해 다시 False로 돌려놓음

        # 지울 숫자가 없으면 평균을 구하고 평균보다 크면 -1, 작으면 +1
        if not once_erased:
            s = sum([sum(row) for row in circle]) / remain
            for row in range(N):
                for col in range(M):
                    if circle[row][col] > s:
                        circle[row][col] -= 1
                    elif 0 < circle[row][col] < s:
                        circle[row][col] += 1

    # 원판의 합을 리턴
    return sum([sum(row) for row in circle])


dx = (0, 1)
dy = (1, 0)
input = sys.stdin.readline
N, M, T = map(int, input().split())  # N=원판의 갯수,M=원판에 적혀있는 수의 갯수,T=회전수
circle = [deque(map(int, input().split()))for _ in range(N)]
erase = [[False for _ in range(M)] for _ in range(N)]  # 지울 숫자임을 표시하는 bool 배열
move = [list(map(int, input().split())) for _ in range(T)]
print(solve())