[백준 17822번] 원판돌리기

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

17822번: 원판 돌리기

 

문제의 예제4를

쭉 캡처해봤습니다.

이 문제를 풀 때 해결해야할 포인트

 

1. 원판돌리기

2. 같은 거 지워주기

3. 평균구한 후 더하거나 뺴기

 

1은 문제 경험이 있다면 비교적 간단합니다.

'어떻게 리스트를 돌리지? 으...복잡해'

물론 리스트를 직접 돌려도 괜찮지만

실수를 간혹하실 수 있습니다.

그래서 간단하게

원판을 deque로 받은 이후에

rotate()를 사용했습니다.

물론 리스트로 받는다면

시계방향은

c[0],c[1:]=c[끝지점],c:[0:끝지점 전]

반시계방향은

c[0],c[1:끝지점 전],c[끝점]=c[1],c[2:끝지점],c[0]

이런 식으로 구현되긴 하는데

이게 실수도 많아

실전에서는 rotate를 쓰면 어떨까하네요.

 

2. 같은 거 지워주는 거

'인접한 거 지워주니

같은 인접한 원판 구해서

쓱쓱 지워주면 되네요'

그런데, 여기서 그냥

'현재 좌표에서 인접한 걸 지운다'

라고 생각해서

'현재 좌표'만을 기준으로 하면

실수를 하실 수 있습니다.

문제의 의도대로라면

동그라미친 1을 기준으로

체크된 모든 부분이 지워집니다.

1이라고 쓰여진 인접한 부분이

저렇게 많기 때문이죠.

그런데 만약에

'현재 좌표'만을 기준으로 삼는다면

빨간색으로 X친 부분만 지워져서

조금 다른 결과를 만들어냅니다.

이건 길찾기나 그룹핑 문제에서 많이 사용했던

BFS로 문제를 풀었습니다.

이 문제에서 주의할 점은

인접한 원판을 구할 때

원판 옆(왼,오),바로 밖의 원판

이렇게만 생각하는 것입니다.

인접하니 '바로 안의 원판'도 생각해야합니다.

계속 정답 40%에서 틀렸습니다가 떠서

어떤 이슈가 있는지 문제를 다시 읽어보니

그런 지점에서 문제점이 있었습니다.

'굳이 저걸 넣어야 동작하나?'

하실 수도 있지만

어찌되었든 문제에서 요구한 FM이 저렇기 때문에

그냥 구현해주면 깔끔할 것 같네요.

 

3. 분배를 하기 전에

2가 동작되었는지 여부를 먼저 체크.

저 같은 경우에는

2동작하면서 total_same이라는 변수를 0으로 선언하고

2가 한번이라도 동작하면

total_same이 1씩 상승하는 걸로 했습니다.

그러니 2를 수행한 이후에

total_same=0라면

2가 동작되지 않았으므로

3을 수행합니다.

여기서는 나누는 걸 조심해야했습니다.

채점하다가 0을 나눴다고 에러가 떠서

원판의 갯수가 0이 아닐 때 

평균을 구하는 걸로 코드를 수정했습니다.

 

# 백준 17822번 원판돌리기
from collections import deque

N, M, T = map(int, input().split())
circle = deque()
circle = [deque(list(map(int, input().split()))) for _ in range(N)]
Turn = []
for _ in range(T):
    x, d, k = map(int, input().split())
    Turn.append([x, d, k])

closer = [(1, 0), (0, 1), (0, -1), (-1, 0)]

i = 1
for t in Turn:
    # 먼저 돌려줌
    X = t[0]
    d = t[1]
    D = 0
    if d == 0:
        D = 1
    elif d == 1:
        D = -1
    K = t[2]
    for c_num in range(1, N + 1):
        if c_num % X == 0:
            for _ in range(K):
                circle[c_num - 1].rotate(D)
    # print(i)
    # print()
    # i+=1
    # print(circle)
    # 인접하면서 같은 수 지우기
    visited = [[False] * M for _ in range(N)]
    total_same = 0
    for r in range(N):
        for c in range(M):
            if visited[r][c] == False and circle[r][c] > 0:
                same = 0
                visited[r][c] = True
                now = circle[r][c]
                # BFS로 구한다.
                q = deque()
                q.append([r, c])
                while q:
                    n_r, n_c = q.popleft()

                    for close in closer:
                        nr = (n_r + close[0])
                        nc = (n_c + close[1]) % M
                        if nr >= N:
                            continue
                        if nr < 0:
                            continue
                        if circle[nr][nc] == now and not visited[nr][nc]:
                            visited[nr][nc] = True
                            circle[nr][nc] = 0
                            same += 1
                            q.append([nr, nc])
                if same > 0:
                    circle[r][c] = 0
                    total_same += 1
                else:
                    visited[r][c] = False
    # print(circle)
    # print()
    # 인접한 게 없는 경우
    # 각 원판의 평균을 구한 후, 평균보다 큰 건 -1,작은 건 +1
    if total_same == 0:
        sum_c = 0
        circle_n = 0
        for r in range(N):
            for c in range(M):
                if circle[r][c]:
                    sum_c += circle[r][c]
                    circle_n += 1
        if circle_n > 0:
            circle_aver = sum_c / circle_n
            # print(circle_aver)
            for r in range(N):
                for c in range(M):
                    if circle[r][c]:
                        if float(circle[r][c]) > circle_aver:
                            circle[r][c] -= 1
                        elif float(circle[r][c]) < circle_aver:
                            circle[r][c] += 1

    # print(circle)
sum_circle = 0
for r in range(N):
    for c in range(M):
        sum_circle += circle[r][c]
print(sum_circle)

 

이 문제의 교훈은

'문제에서 구현하라는 건

어지간하면 다 구현하자'는 것.

제 기준에서는

굳이 안쪽 원판까지 판단해야하나 싶었지만

저렇게 구현해야 정답이 나왔으니

뭐...구현하는 게 맞긴..하네요...ㅎ