[Python] 백준 17822 원판 돌리기
https://www.acmicpc.net/problem/17822
원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.
- 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
- 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
- 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
- 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 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을 통해 틀린 부분을 정정.
일찍 풀어서 놀 시간이 많아져 행복하다.
Author And Source
이 문제에 관하여([Python] 백준 17822 원판 돌리기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@attractive_minki/Python-백준-17822-원판-돌리기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)