[221003] 백준 17822 : 원판 돌리기

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

17822번: 원판 돌리기

1. 조건을 잘 봅시다!

 i, j, N, M 난무하니까 처음 읽었을 때에는 덜컥 겁이 났다. 하지만 아주 천천히 읽어보면 친절하게 말해준 조건들이다.

첫 3번째 조건은 다음과 같다.

• (i, 1)은 (i, 2), (i, M)과 인접하다.
• (i, M)은 (i, M-1), (i, 1)과 인접하다.
• (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)

임의의 포인트를 선택했을 때 인접한 경우를 빨간 원으로 표시

이 말은 임의의 원판을 기준으로 했을 때 조건이다. 3번째 조건이 일반적인 조건문이고, 위의 둘은 원판의 첫 번째 인덱스와 M번째 인덱스의 경우에 인접하다는 것을 보여주는 말이다. 당연한 말을 수식으로 설명하니 더 어렵게 느껴질 수도 있다. 그다음 3번째 조건은 다음과 같다.

• (1, j)는 (2, j)와 인접하다.
• (N, j)는 (N-1, j)와 인접하다.
• (i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)

 해당 조건은 원판 간의 관계를 말해주는 조건이다. 첫 번째 원판은 2번째 원판과만 인접해있고, 마지막 원판은 그 앞에 원판만 인접해있다는 것을 알고 있으면 된다. 단일 원판 기준으로 인접구간을 설명했을 때, 원판 간의 관계에서는 다르게 적용된다는 것을 잘 알려주고 있는 조건문이다.

왼쪽은 처음 원판과 끝 원판 기준으로 인접한 경우, 오른쪽은 가운데 판을 기준으로 인접한 경우를 표시

그렇다면 인접 값 찾는 것은 어떻게 해야할까?

나는 해당 문제에 대해 각 원판들을 하나의 리스트로 표현하였다. 백준 23288에서 주사위 굴릴 때처럼 append, del, insert를 활용해서 구현하였다. 이렇게 하면 인접 항 찾을 때도 인덱싱 번호에서 -1, +1 계산만 해주면 된다. 이때, 원판 안에서는 인덱스 번호가 넘어갈 때 보정을 해주면 되고, 원판끼리의 관계를 찾을 때에는 벗어나는 조건에 대해 계산을 안 하도록 하면 된다. 샘플 코드 예시는 다음과 같다.

ni, mi= [-1, 1], [-1, 1]
for i in range(N):
    for j in range(M):
        # choose 1 point
        if board[i][j] != 'X':
            x, y = i, j
            num = board[x][y]
            # 자기 자신을 기준으로 탐색
            for my in range(2) :
                nx = x
                ny = y + mi[my]
                while ny >= M : ny -= M
                while ny < 0 : ny += M
                if num == board[nx][ny] :
                    temp.append([nx, ny])
            # 원판끼리 탐색
            for nx in range(2) :
                nx = x + ni[nx]
                ny = y
                if 0 <= nx < N :
                    if num == board[nx][ny] :
                        temp.append([nx, ny])

2. 주의해야 할 점!

"원판의 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다." 중 2번째 조건

"없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다."

 

왜 문제가 될까?

바로 원판의 수가 없는 환경에서도 원판은 돌아갈 수 있기 때문이다!

그때 평균을 구하면 Zero-Division Error 가 나오기 때문에 이 점을 조심해서 코딩해야 한다.

 

3. 전체 코드

메모리 : 116284 KB, 시간 : 204 ms, 풀이 시간 : 73 min

N, M, T = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
calc_info = [list(map(int, input().split())) for _ in range(T)]

# 상, 우, 하, 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def turn(xi, di, ki):
    # xi 의 배수가 되는 원판을 di 방향으로 ki 번 돌린다.
    itk = 1
    it = itk * xi
    while it -1 < len(board):
        temp = board[it-1].copy()
        for _ in range(ki):
            if di == 0 : # 시계 방향
                temp.insert(0, temp[-1])
                del temp[-1]
            else : # 반시계방향
                temp.append(temp[0])
                del temp[0]
        # 다 돌렸다
        for i in range(M):
            board[it -1][i] = temp[i]
        itk += 1
        it = itk * xi

def adjacent() :
    temp = []
    ni, mi= [-1, 1], [-1, 1]
    for i in range(N):
        for j in range(M):
            # choose 1 point
            if board[i][j] != 'X':
                x, y = i, j
                num = board[x][y]
                # 자기 자신을 기준으로 탐색
                for my in range(2) :
                    nx = x
                    ny = y + mi[my]
                    while ny >= M : ny -= M
                    while ny < 0 : ny += M
                    if num == board[nx][ny] :
                        temp.append([nx, ny])
                # 원판끼리 탐색
                for nx in range(2) :
                    nx = x + ni[nx]
                    ny = y
                    if 0 <= nx < N :
                        if num == board[nx][ny] :
                            temp.append([nx, ny])
    if temp :
        for x, y in temp :
            board[x][y] = 'X'
    else :
        total = 0
        cnt = 0
        for i in range(N):
            for j in range(M):
                if board[i][j] != 'X' :
                    total += board[i][j]
                    cnt += 1
        if cnt > 0 :
            average = total / cnt
            for i in range(N):
                for j in range(M):
                    if board[i][j] != 'X':
                        if board[i][j] < average :
                            board[i][j] += 1
                        elif board[i][j] > average :
                            board[i][j] -= 1

def solve() :
    for x, d, k in calc_info :
        turn(x, d, k)
        adjacent()
    result = 0
    for i in range(N):
        for j in range(M):
            if board[i][j] != 'X':
                result += board[i][j]
    print(result)

solve()