[Python] 백준 17822 원판 돌리기

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

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

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

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

특이사항
열끼리는 끝과 끝 인접 인정
행끼리는 끝과 끝 인접 인정하지 않음.
ex) numbers[0][0]과 numbers[0][M - 1] -> 인접
numbers[0][0]과 numbers[N - 1][0] -> 인접 X

# 17822 원판 돌리기

# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

N, M, T = map(int, input().split())
numbers = [list(map(int, input().split())) for _ in range(N)]
xi = list()
di = list()
ki = list()
for _ in range(T):
    tx, td, tk = map(int, input().split())
    xi.append(tx)
    di.append(td)
    ki.append(tk)
    
for i in range(T):
    # 원판 배수
    cur_x = xi[i]
    # 방향 0: 시계, 1: 반시계
    cur_d = di[i]
    # 회전 칸수
    cur_k = ki[i]
    
    # 1. 배수 원판 회전시키기.
    # 시계 방향으로 회전
    if cur_d == 0:
        # idx가 0부터 시작하므로 cur_x - 1부터 시작한다고 표현
        for j in range(cur_x - 1, N, cur_x):
            # cur_k만큼 시계방향으로 회전
            for _ in range(cur_k):
                temp = numbers[j].pop()
                numbers[j].insert(0, temp)
    
    # 반시계 방향으로 회전
    elif cur_d == 1:
        # idx가 0부터 시작하므로 cur_x - 1부터 시작한다고 표현
        for j in range(cur_x - 1, N, cur_x):
            # cur_k만큼 반시계방향으로 회전
            for _ in range(cur_k):
                temp = numbers[j].pop(0)
                numbers[j].append(temp)

    # 2. 원판에 수가 남아있으면, 인접하면서 수가 같은 것을 모두 찾는다.
    temp_num = 0
    for num in numbers:
        temp_num += sum(num)
    # 원판에 수가 없으면 break
    if temp_num == 0:
        break
    
    # 인접하면서 수가 같은 것을 모두 찾는다.
    visited = [[0] * (M) for _ in range(N)]
    for r in range(N):
        for c in range(M):
            if numbers[r][c] == 0 or visited[r][c] == 1:
                continue
            queue = [(r, c)]
            while queue:
                kr, kc = queue.pop()
                
                for k in range(4):
                    current_r = kr + dr[k]
                    current_c = kc + dc[k]
                    # 열끼리 연산
                    if current_c < 0:
                        current_c = M - 1
                    elif current_c > M - 1:
                        current_c = 0
                    if 0 <= current_r and current_r < N and visited[current_r][current_c] == 0:
                        # 인접한 것끼리 숫자가 같을 경우
                        if numbers[kr][kc] == numbers[current_r][current_c]:
                            # 방문 처리
                            visited[kr][kc] = 1
                            visited[current_r][current_c] = 1
                            queue.append((current_r, current_c))
    # visited한 것이 있으면 == 인접한 것이 있으면 0으로 만듦.
    check = 0
    for rr in range(N):
        for cc in range(M):
            if visited[rr][cc] == 1:
                numbers[rr][cc] = 0
                check = 1
    # 인접한 수가 없다면 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.
    if check == 0:
        avg = 0
        cnt = 0
        # 평균 계산
        for rr in range(N):
            for cc in range(M):
                if numbers[rr][cc] != 0:
                    avg += numbers[rr][cc]
                    cnt += 1
        # 평균과 비교   
        avg /= cnt
        for rr in range(N):
            for cc in range(M):
                if numbers[rr][cc] != 0:
                    # 평균보다 크면 1 빼줌
                    if numbers[rr][cc] > avg:
                        numbers[rr][cc] -= 1
                    # 평균보다 작으면 1 더해줌
                    elif numbers[rr][cc] < avg:
                        numbers[rr][cc] += 1

ans = 0
for idx in range(N):
    ans += sum(numbers[idx])
print(ans)

풀면서 틀렸던 부분
1.

for k in range(4):
   	current_r = kr + dr[k]
   	current_c = kc + dc[k]

어리석게도 kr, kc 대신 numbers[kr][kc]를 넣어서 한참 고생했다.
BFS를 오랜만에 풀어서 생긴 참사로 보인다,,,
에러 고치는 데 10여 분 정도 소요되었다.
_
2.

# visited한 것이 있으면 == 인접한 것이 있으면 0으로 만듦.
# 인접한 수가 없다면 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

다음 연산들의 들여쓰기(indentation)을 실수로 두 칸 더 넣었다. 즉, 이중 for문 안에 저 연산을 해주었다.

두 번째 예제를 넣었을 때, visited 배열 모두 0으로 인식되어, 터진 배열이 없는 것으로 인식되어 이상한 출력이 자꾸 나왔다.
5분 정도 헤매다가 오답을 찾았다.
_
3.

# 시계 방향으로 회전
    if cur_d == 0:
        # idx가 0부터 시작하므로 cur_x - 1부터 시작한다고 표현
        for j in range(cur_x - 1, N, cur_x):
            # cur_k만큼 시계방향으로 회전
            for _ in range(cur_k):
                temp = numbers[j].pop()
                numbers[j].insert(0, temp)
# 반시계 방향도 틀렸지만, 큰 틀에서 코드는 같으므로 생략

for j in range(cur_x - 1, M + 1, cur_x): 로 짰었다.
제출 이후 IndexError가 발생했다.

vscode에서 N=4, M=4에서 N=3으로 바꾼 뒤 실행해보고, 금방 에러를 찾았다.

참사가 난 이유:
1. N, M 값을 명확히 구분하지 않고 문제를 풀었다.
1-1. 주어진 예시에선 N = M이므로 IndexError를 발견하기 쉽지 않았다. 내가 따로 체크했어야 했다.
2. 맨 처음에 위, 왼쪽에 0 padding을 넣어, numbers[1][1]이 첫 값이 되도록 만드려고 했다.
시계/반시계 방향 회전을 구현하는 과정에서 pop, insert, append 등을 써야하는 것을 깨달았고, padding 없이 짜기로 했으면서, for 문 안의 +1을 그대로 냅뒀다.

풀면서 주의했던 부분
1. 저번 문제에서 i를 중복해서 사용하는 바람에, i 값이 예상하지 못하게 엄청 튀었던 경험이 있다.
이번에도 for i in range(): 안에서 for i in range():를 썼다가, 코드를 전체적으로 훑어보는 과정에서 위의 문제가 생각나 self-debugging에 성공했다.
_
2.

# 원판에 수가 없으면 break
    if temp_num == 0:
        break

개인적으로 이 부분에 대한 문제의 설명이 모호해보였다. 먼저 탈출해도 되나? 큰 문제가 없다고 판단하여 break를 걸었고, 예상대로 문제 없어보인다.
_
3.

queue = [(r, c)]
while queue:
	kr, kc = queue.pop()

맨 처음엔 이중 for문만으로 풀려고 시도하다가, queue를 이용한 BFS가 나을 것이라고 생각 후 코드를 고쳤다.
무려 5중 반복문을 사용하면서(for k in range(4)도 아무튼 반복문임.), 시간복잡도가 버텨낼지에 대한 의문도 있어 계산해보았다.

2 ≤ N, M ≤ 50, 최대 50
50 ** 5 = 10 ** 5 * 5 ** 5
10 ** 5 = 100,000
5 ** 5 = 대충 3125
3억의 시간복잡도가 소요된다... 문제 풀면서 10 ** 5는 1만이었는데... 잘못 계산한 것 같다.

5중 반복문이 아니라 4중 반복문인가보다!

50 ** 4 * 4 = 10 ** 4 * 5 ** 4 * 4
10 ** 4 = 10,000
5 ** 4 = 625
625 * 4 = 대충 3,000
10,000 * 3,000 = 30,000,000 = 3천만 < 1억

따라서, 시간복잡도 문제는 고려하지 않아도 된다! 만세!

-- 후기 --

골드 1 문제를 풀다가 골드 3 문제를 푸니 상대적으로 쉽게 해결한 느낌이다.

문제를 풀면서 발생한 소소한 참사들을 기록해놓고, 다음에 실수하지 않도록 해야겠다.

p.s) 대참사 == 백준 질문검색 란에서 반례를 찾는 것.
소소한 참사 == 한 번에 문제를 풀진 못했지만, self debugging을 통해 틀린 부분을 정정.

일찍 풀어서 놀 시간이 많아져 행복하다.