[파이썬] 17822. 원판 돌리기

문제

반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다.

• (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)
• (1, j)는 (2, j)와 인접하다.
• (N, j)는 (N-1, j)와 인접하다.
• (i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)

아래 그림은 N = 3, M = 4인 경우이다.

 

원판의 회전은 독립적으로 이루어진다. 2번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키기 전과 일치해야 한다.

다음 그림은 원판을 회전시킨 예시이다.

 

 

원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.

1. 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
2. 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
   1. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
   2. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.

입력

첫째 줄에 N, M, T이 주어진다.

둘째 줄부터 N개의 줄에 원판에 적힌 수가 주어진다. i번째 줄의 j번째 수는 (i, j)에 적힌 수를 의미한다.

다음 T개의 줄에 xi, di, ki가 주어진다.

출력

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 출력한다.

제한

• 2 ≤ N, M ≤ 50
• 1 ≤ T ≤ 50
• 1 ≤ 원판에 적힌 수 ≤ 1,000
• 2 ≤ xi ≤ N
• 0 ≤ di ≤ 1
• 1 ≤ ki < M

 

예제 입력 1 

4 4 1
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1

예제 출력 1 

30

원판의 초기 상태는 다음과 같다.

 

예제 입력 2 

4 4 2
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
3 1 3

예제 출력 2 

22

예제 1에서 이어진다.

 

 

 

예제 입력 3 

4 4 3
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
3 1 3
2 0 2

예제 출력 3 

22

예제 2에서 이어진다.

 

 

예제 입력 4 

4 4 4
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
3 1 3
2 0 2
3 1 1

예제 출력 4 

0

예제 3에서 이어진다.

 

 

예제 입력 5 

4 6 3
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8
4 5 6 7 8 9
2 1 4
3 0 1
2 1 2

 

예제 출력 5 

26

 

 

🌱 나의 풀이

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, T = map(int, input().split())  # 반지름, 정수의 개수, 회전 횟수
circles = [list(map(int, input().split())) for n in range(N)]  # 원판
rotations = [list(map(int, input().split())) for t in range(T)]  # 회전 정보
cnt_nums = N * M

def right(i, k):
    tmp = [0] * M
    for idx in range(M):
        tmp[(idx + k) % M] = circles[i][idx]
    return tmp

def left(i, k):
    tmp = [0] * M
    for idx in range(M):
        tmp[(idx - k) % M] = circles[i][idx]
    return tmp

def remove_two(i1, j1, i2, j2):
    circles[i1][j1] = 0
    circles[i2][j2] = 0

def dfs(i, j, value):
    global flag
    for ni, nj in [(i, j-1), (i, j+1), (i-1, j), (i+1, j)] :
        if ni == -1 or ni == N : continue
        if circles[ni % N][nj % M] == value :
            flag = True
            circles[ni % N][nj % M] = 0
            dfs(ni % N, nj % M, value)

def total():
    answer = 0
    cnt_zero = 0
    for i in range(N):
        for j in range(M):
            if circles[i][j] == 0:
                cnt_zero += 1
                continue
            answer += circles[i][j]
    return answer, cnt_zero

def none_result(average):
    for i in range(N):
        for j in range(M):
            if circles[i][j] == 0:
                continue
            # 평균보다 크거나 작을 때
            if circles[i][j] > average:
                circles[i][j] -= 1
            elif circles[i][j] < average:
                circles[i][j] += 1

for x, d, k in rotations:
    for i in range(x - 1, N, x):
        if d == 0:  # 시계 방향
            circles[i] = right(i, k)
        else:
            circles[i] = left(i, k)
    flag = False
    for i in range(N) :
        for j in range(M) :
            if circles[i][j] != 0 :
                dfs(i, j, circles[i][j])
    if not flag :       # 삭제한 수가 없을 때
        sum_circles, cnt_zero = total()
        if sum_circles == 0 : continue
        average = sum_circles / (cnt_nums - cnt_zero)
        none_result(average)

print(total()[0])

이 문제는 회전, 인접한 같은 수 제거를 구현하는 게 핵심이다.

특히 인접한  같은 수 제거하는 부분을 시간 초과가 안 나도록 해야한다.

🟨 회전

• left, right 메소드 구현
• tmp[(idx + k) % M] = circles[i][idx]
  • 인덱스 idx에 k만큼 더한다. (=오른쪽으로 k만큼 이동)
  • 나머지 연산자 %M을 이용
    • ex) M=3, idx=2, k=2일 때 (2+2) % 3 = 1

🟥 인접한 같은 수 제거

• dfs
• flag는 인접한 같은 수를 한 번이라도 제거했는지 나타내는 boolean
• i, j의 상하좌우를 탐색
• 나머지 연산자 이용
• 인접한 원판(행 i가 다른)을 탐색할 때 주의한다.
  • if ni == -1 or ni == N : continue
    • 0번째 원판과 N번째 원판은 서로 인접하지 않기 때문이다.

 

 

# 틀렸습니다
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, T = map(int, input().split())  # 반지름, 정수의 개수, 회전 횟수
circles = [list(map(int, input().split())) for n in range(N)]  # 원판
rotations = [list(map(int, input().split())) for t in range(T)]  # 회전 정보
cnt_nums = N * M

def right(i, k):
    tmp = [0] * M
    for idx in range(M):
        tmp[(idx + k) % M] = circles[i][idx]
    return tmp

def left(i, k):
    tmp = [0] * M
    for idx in range(M):
        tmp[(idx - k) % M] = circles[i][idx]
    return tmp

def remove_two(i1, j1, i2, j2):
    circles[i1][j1] = 0
    circles[i2][j2] = 0

def dfs(i, j, value):
    global flag
    for ni, nj in [(i, j-1), (i, j+1), (i-1, j), (i+1, j)] :
        if circles[ni % N][nj % M] == value :
            flag = True
            circles[ni % N][nj % M] = 0
            dfs(ni % N, nj % M, value)

def total():
    answer = 0
    cnt_zero = 0
    for i in range(N):
        for j in range(M):
            if circles[i][j] == 0:
                cnt_zero += 1
                continue
            answer += circles[i][j]
    return answer, cnt_zero

def none_result(average):
    for i in range(N):
        for j in range(M):
            if circles[i][j] == 0:
                continue
            # 평균보다 크거나 작을 때
            if circles[i][j] > average:
                circles[i][j] -= 1
            elif circles[i][j] < average:  
                circles[i][j] += 1

for x, d, k in rotations:
    for i in range(x - 1, N, x):
        if d == 0:  # 시계 방향
            circles[i] = right(i, k)
        else:
            circles[i] = left(i, k)
    flag = False
    for i in range(N) :
        for j in range(M) :
            if circles[i][j] != 0 :
                dfs(i, j, circles[i][j])
    if not flag :       # 삭제한 수가 없을 때
        sum_circles, cnt_zero = total()
        if sum_circles == 0 : continue
        average = sum_circles / (cnt_nums - cnt_zero)
        none_result(average)

print(total()[0])

테케 1번이30이 아니고 24가 나온다.

dfs가 잘못됨

 

# 시간 초과
import sys
input = sys.stdin.readline

N, M, T = map(int, input().split())  # 반지름, 정수의 개수, 회전 횟수
circles = [list(map(int, input().split())) for n in range(N)]  # 원판
rotations = [list(map(int, input().split())) for t in range(T)]  # 회전 정보
cnt_nums = N * M

def right(i, k):
    tmp = [0] * M
    for idx in range(M):
        tmp[(idx + k) % M] = circles[i][idx]
    return tmp

def left(i, k):
    tmp = [0] * M
    for idx in range(M):
        tmp[(idx - k) % M] = circles[i][idx]
    return tmp

def remove_two(i1, j1, i2, j2):
    circles[i1][j1] = 0
    circles[i2][j2] = 0

def dfs(i, j):
    global remove_lst
    
    if i == N:
        return

    if j == M:
        return

    if i != 0 and circles[i][j] == circles[i - 1][j] != 0:
        remove_lst.update([(i, j), (i - 1, j)])

    if i < N - 1 and circles[i][j] == circles[i + 1][j] != 0:
        remove_lst.update([(i, j), (i + 1, j)])

    if circles[i][j - 1] == circles[i][j] != 0:
        remove_lst.update([(i, j), (i, j - 1)])

    if j < M - 1 and circles[i][j + 1] == circles[i][j] != 0:
        remove_lst.update([(i, j), (i, j + 1)])

    dfs(i + 1, j)
    dfs(i, j + 1)

def total():
    answer = 0
    cnt_zero = 0
    for i in range(N):
        for j in range(M):
            if circles[i][j] == 0:
                cnt_zero += 1
                continue
            answer += circles[i][j]
    return answer, cnt_zero

def none_result(average):
    for i in range(N):
        for j in range(M):
            if circles[i][j] == 0:
                continue
            if circles[i][j] > average:
                circles[i][j] -= 1
            elif circles[i][j] < average :      # else로 하면 안 된다
                circles[i][j] += 1

for x, d, k in rotations:
    for i in range(x - 1, N, x):
        if d == 0:  # 시계 방향
            circles[i] = right(i, k)
        else:
            circles[i] = left(i, k)

    remove_lst = set()
    dfs(0, 0)

    if remove_lst:
        while remove_lst:
            i, j = remove_lst.pop()
            circles[i][j] = 0
    else:
        sum_circles, cnt_zero = total()
        average = sum_circles / (cnt_nums - cnt_zero)
        none_result(average)

print(total()[0])

재귀 깊이를 늘려줘도 시간 초과 또는 메모리 초과가 뜬다.

DFS만 계산해도 50^4*4다. 테스트케이스 50개마다 50개의 점마다 상하좌우를 탐색한다.

파이썬은 1초에 2천만 번이라고 생각하면 되는데 넘어가는 수치다.

DFS에서 한번에 모든 인접한 같은 수를 가진 점을 찾는 게 문제다.

 

# 틀렸습니다
import sys
input = sys.stdin.readline

N, M, T = map(int, input().split())     # 반지름, 정수의 개수, 회전 횟수
circles = [list(map(int, input().split())) for n in range(N)]       # 원판
rotations = [list(map(int, input().split())) for t in range(T)]     # 회전 정보
cnt_nums = N * M

def right(i, k) :
    tmp = [0] * M
    for idx in range(M):
        tmp[(idx + k) % M] = circles[i][idx]
    return tmp

def left(i, k) :
    tmp = [0] * M
    for idx in range(M):
        tmp[(idx - k) % M] = circles[i][idx]
    return tmp

def remove_two(i1, j1, i2, j2) :
    circles[i1][j1] = 0
    circles[i2][j2] = 0

def dfs(i, j) :
    global remove_lst
    if i == N :
        return

    if j == M :
        return

    if i != 0 and circles[i][j] == circles[i - 1][j] != 0 :
        remove_lst.update([(i, j), (i-1, j)])

    if i < N-1 and circles[i][j] == circles[i + 1][j] != 0 :
        remove_lst.update([(i, j), (i + 1, j)])

    if circles[i][j - 1] == circles[i][j] != 0 :
        remove_lst.update([(i, j), (i, j-1)])

    if j < M-1 and circles[i][j + 1] == circles[i][j] != 0 :
        remove_lst.update([(i, j), (i, j + 1)])

    dfs(i + 1, j)
    dfs(i, j + 1)

def total() :
    answer = 0
    cnt_zero = 0
    for i in range(N):
        for j in range(M) :
            if circles[i][j] == 0 :
                cnt_zero += 1
                continue
            answer += circles[i][j]
    return answer, cnt_zero

def none_result(average) :
    for i in range(N) :
        for j in range(M) :
            if circles[i][j] == 0 :
                continue
            if circles[i][j] > average :
                circles[i][j] -= 1
            else :
                circles[i][j] += 1

for x, d, k in rotations :
    for i in range(x-1, N, x) :
        if d == 0 :     # 시계 방향
            circles[i] = right(i, k)
        else :
            circles[i] = left(i, k)

    remove_lst = set()
    dfs(0, 0)
    
    if remove_lst :
        while remove_lst :
            i, j = remove_lst.pop()
            circles[i][j] = 0
    else :
        sum_circles, cnt_zero = total()
        average = sum_circles / (cnt_nums - cnt_zero)
        none_result(average)

print(total()[0])

마지막 테케만 틀려

26이 아니라 47이 나온다....

다른 사람이 작성한 거 실행하면 원판이 아래와 같은 상태가 되어야 한다.

[deque([2, 3, 4, 5, 5, 5]), deque([5, 6, 3, 4, 5, 5]), deque([4, 5, 5, 5, 6, 7]), deque([7, 8, 5, 5, 5, 6])]
[deque([2, 3, 4, 0, 0, 0]), deque([0, 6, 3, 4, 0, 0]), deque([0, 4, 0, 0, 0, 0]), deque([0, 8, 0, 0, 0, 0])]
[deque([2, 3, 4, 0, 0, 0]), deque([3, 0, 0, 0, 0, 6]), deque([0, 0, 0, 0, 0, 0]), deque([0, 0, 0, 0, 0, 8])]

나는

[[2, 3, 4, 5, 6, 5], [5, 6, 3, 4, 5, 6], [4, 5, 6, 5, 6, 7], [7, 8, 5, 6, 5, 6]]
[[2, 3, 4, 5, 6, 5], [5, 6, 3, 4, 0, 0], [0, 4, 0, 0, 0, 0], [0, 8, 0, 0, 0, 0]]

[[2, 3, 4, 5, 6, 5], [3, 0, 0, 0, 5, 6], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 8]]

원인은 none_result 메소드에서 else문 때문이다.

평균이 5라면 5는 넘어가야 하는데 +1을 시키니까 잘못됨

 

 

📌 다른 사람 풀이

# https://hoyeonkim795.github.io/posts/17822/
import sys
from collections import deque
n, m, t = map(int, input().split())     # 원판의 개수, 원판에 적힌 정수의 개수, T번 회전
board = [deque(int(x) for x in input().split()) for _ in range(n)]
info = [[int(x) for x in input().split()] for _ in range(t)]    # x배수, d방향, k칸 회전
# d == 0 시계 방향 d == 1 반시계 방향

for tc in range(t) :
    x, d, k = info[tc]
    # 회전하기
    result = 0
    for i in range(n) :
        result += sum(board[i])
        if (i + 1) % x == 0 :
            if d == 0 :
                board[i].rotate(k)
            else :
                board[i].rotate(-k)

    # 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
    if result != 0 :
        # 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
        have_to_remove = []
        # 먼저 같은 원내에서 인접한 애들
        for i in range(n) :
            for j in range(m - 1) :
                if board[i][j] != 0 and board[i][j + 1] != 0 and board[i][j] == board[i][j + 1] :
                    have_to_remove.append((i, j))
                    have_to_remove.append((i, j+1))
            if board[i][0] != 0 and board[i][-1] != 0 and board[i][0] == board[i][-1] :
                have_to_remove.append((i, 0))
                have_to_remove.append((i, m - 1))

        # 옆의 원
        for j in range(m) :
            for i in range(n - 1) :
                if board[i][j] != 0 and board[i + 1][j] != 0 and board[i][j] == board[i + 1][j] :
                    have_to_remove.append((i, j))
                    have_to_remove.append((i + 1, j))

        # 원판 다시 만들어주기
        have_to_remove = list(set(have_to_remove))

        for i in range(len(have_to_remove)) :
            x, y = have_to_remove[i]
            board[x][y] = 0

        # 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.
        if len(have_to_remove) == 0 :
            avg_sum = 0
            zero_cnt = 0
            for i in range(n) :
                avg_sum += sum(board[i])
                zero_cnt += board[i].count(0)
            avg = avg_sum / (n * m - zero_cnt)

            for i in range(n) :
                for j in range(m) :
                    if board[i][j] != 0 and board[i][j] > avg :
                        board[i][j] -= 1
                    elif board[i][j] != 0 and board[i][j] < avg :
                        board[i][j] += 1
    else :
        break

ans = 0
for i in range(n) :
    ans += sum(board[i])

print(ans)

회전은 파이썬의 rotate 메서드를 사용했다.

인접한 같은 수를 제거하는 것은 반복문 사용

 

 

# https://jjangsungwon.tistory.com/68
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)

DFS로 상하좌우를 탐색하며 어떤 수 array[i][j]와 인접한 같은 수를 지운다.

나는 DFS를 인접한 같은 수를 모두 찾도록 해서 시간초과가 나는구나..

 

 

문제 출처 👉 백준