[백준17822&파이썬] 원판을 돌릴때는 deque와 원형큐를 연상해보자

# 문제

백준 17822 원판 돌리기

17822번: 원판 돌리기

# 코드

import sys
from collections import deque

def print2D(arr):
  print("--")
  for i in range(len(arr)):
    for j in range(len(arr[i])):
      print(arr[i][j], end=" ")
    print()
# 회전 방향 정의
TURN_RIGHT = 0 # 시계방향
TURN_LEFT = 1 # 반시계방향

# 탐색 방향 정의
dirs = [
    (-1,0),(0,1),(1,0),(0,-1)
]

board = list()
N,M,T = map(int,sys.stdin.readline().split())
for _ in range(N) :
    dq = deque()
    temp = list(map(int,sys.stdin.readline().split()))
    dq.extend(temp)
    board.append(dq)

# T번 회전시키는 커맨드를 수행함
for _ in range(T) :
    x,d,k = map(int,sys.stdin.readline().split())
    for i in range(x,N+1,x) : # x 배수
        idx = i-1 # 배열의 배수가 0부터 시작하기 떄문에 숫자를 보정해줌
        # 해당 인덱스에 관해서 로테이트를 k칸 수행해야함.

        if d == TURN_RIGHT : # (시계)
            board[idx].rotate(k)
        else : # TURN_LEFT (반시계)
            board[idx].rotate(-1*k)

    # 회전이 끝난 상태. 인접수에 대한 처리를 시작해야함.
    # BFS를 이용해서 인접수에 대한 검사를 진행한다.
    sum = 0
    postiveNumberCount = 0
    removeCount = 0
    for row in range(N) :
        for col in range(M) :
            curTarget = board[row][col]
            if curTarget == -1 :
                continue
            sum += board[row][col] if board[row][col] != -1 else 0 # 모든 곳을 순회하게 되기 떄문에
            postiveNumberCount += 1 if board[row][col] != -1 else 0 # 나눠줄 수
            dq = deque()
            dq.append([row,col])
            # dq가 빌때까지 BFS탐색을 시작한다.
            while len(dq) != 0 :
                _row,_col = dq.popleft()
                # 4방향을 살펴본다.
                for dir in dirs :
                    next = [_row+dir[0], _col+dir[1]]
                    # col값을 보정해준다
                    if next[1] == -1 :
                        next[1] = M-1
                    if next[1] == M :
                        next[1] = 0
                    if 0<= next[0] < N and 0<= next[1] < M and board[next[0]][next[1]] == curTarget :
                        # 인접한 수가 같은 수라면 지워준다.
                        # 여기서는 현재의 값이 지워진다.
                        board[_row][_col] = -1 # -1을 표기하여 지워준다
                        board[next[0]][next[1]] = -1 # 다음꺼도 미리 지워준다.
                        dq.append(next)
                        removeCount +=1

    if removeCount == 0 and postiveNumberCount > 0:
        # 지운게 하나도 없는경우 평균을 구해야 한다.
        _avg = sum / postiveNumberCount
        for subRow in range(N) :
            for subCol in range(M) :
                pivot = board[subRow][subCol]
                if board[subRow][subCol] != -1:
                    if pivot < _avg :
                        board[subRow][subCol] +=1
                    if pivot > _avg :
                        board[subRow][subCol] -= 1
    # print2D(board)

# 최종 합을 구해서 답을 구한다.
result = 0
for row in range(N) :
    for col in range(M) :
        result += board[row][col] if board[row][col] != -1 else 0

# print2D(board)
print(result)



# 런타임 에러 (ZeroDivisionError) 발생 어디서 발생하는걸까>?
# -> 모든곳이 -1로 다 변해버린 상황이라면 sum과 postiveCount가 초기값이 0인 상태이고 이럴떄 ZeroDivisionError가 발생할 것으로 추정 됨
# 그렇기 때문에 해당 경우를 처리하기 위해서 if removeCount == 0 and 'postiveNumberCount' > 0: 조건을 추가함.

# 풀이

이 문제를 풀기위해서는 

1. 원판을 어떻게 구성해야하는가?
2. 인접수는 무엇이고 인접수를 어떻게 찾아낼 것인가? 

에 대해서 고민하면 된다. 원판을 돌려야한다는 특성이 있기 때문에 난 양쪽에서 pop, append가 가능한 deque를 하나의 원판으로 생각했고 해당 deque를 배열에 담아줌으로써 N개의 원판을 구성시켰다. 

 왜냐하면 인접수를 확인할때 현재 위치에서 4방향 탐색을 진행하는것과 똑같기 때문이다. 다만 원형이기 떄문에 배열맨끝에서 인덱스 하나를 높이면 OutOfBound가 아니라 인덱스 0을 살펴야 한다. 0의 경우도 -가 된다면 -1이 아니라 맨 끝으로 가야한다. 이 표현은 col값을 보정해준다면 충분히 가능하다. 쉽게 말해 원형큐처럼 구성해주면 된다. 어차피 입력값이 정직하게 보장되기 때문에 ==-1, ==M으로해서 보정해줬다.

# col값을 보정해주자
            while len(dq) != 0 :
                _row,_col = dq.popleft()
                # 4방향을 살펴본다.
                for dir in dirs :
                    next = [_row+dir[0], _col+dir[1]]
                    # col값을 보정해준다
                    if next[1] == -1 :
                        next[1] = M-1
                    if next[1] == M :
                        next[1] = 0

 회전시키기 위해서 옛날에는 직접 pop, appendleft와 같이 구현했었는데 그렇게 풀고나서 deque에 rotate라는 아주 편리한 메소드를 지원하는 사실을 알게 됐다. 더 엄청난건 음/양으로 나누어 시계방향, 반시계방향 회전을 지원한다.

        if d == TURN_RIGHT : # (시계)
            board[idx].rotate(k)
        else : # TURN_LEFT (반시계)
            board[idx].rotate(-1*k)

 마지막으로 인접수들 확인은 BFS 돌렸다.  이후 지운게 없다면 평균을 구해야하는데 여기서 반복문 한번 더해서 지워지지않은 수의 평균을 구하기 위해서 반복문 한번더 돌리는게 싫어서 BFS돌리기 위해서 2중포문으로 완전탐색할때 미리 구해놓도록 했다. 

## 에러 (ZeroDivisionError)

말그대로 ZeroDivisionError가 발생했다. 내 코드에서 나눗셈을 수행하는 곳은 

_avg = sum / postiveNumberCount

 위의 존재하는 단 한 곳뿐이다. 분명히 sum이 0이 되는순간이 존재하지 않을 것이라고 생각했다. 왜냐면 애초에 원판에 입력되는 값(M)이 1이상이기 때문에 평균은 무조건 1이 넘고 그렇기 떄문에 여기서 -1을해서 0이 되는경우는 존재하지않을 것이라고 생각했다. 반은 맞고 반은 틀렸던 생각이다. 위의 케이스로 해당하여 0이 되는순간은 존재하지 않지만, 모든 수들을 다 지워져버렸을때를 생각하지 못했다.

 모든 수들이 다 지워진 상태라면 removeCount가 당연히 0이되어 해당 분기문 안으로 들어갈 것이지만, sum은 초기값 0일 것이다. 그래서 해당 부분에 postiveNumberCount > 0 의 조건을 추가했다. 

if removeCount == 0 and postiveNumberCount > 0:

 

# 여담

 곧 SKT 주니어 텔렌트 채용이 시작되고 다시금 코테를 바짝 준비해야할 필요성이 느껴졌다. 물른 스트릭은 어찌저찌 유지 중이긴 했지만 퇴근하고 쉬운문제 위주로 풀었다. 이전에 풀던 SW삼성 기출문제 중 못풀었던 문제를 다시 풀고 있다. SKT는 내가 제일 가고 싶은 회사이기 때문이다.

 저번 SK브로드밴드 코테를 볼때 무슨 원판 같은거 막 돌리는 문제 만나서 처음 보는 유형이기도 하고 어떻게 해야하는지 감도 안잡혀서 다른거 풀었던 기억이 있었다. 꾸준히 코딩테스트 문제 풀면서 느끼는거지만 이것도 신유형이 아니라 많이 나오는 유형이었다.

 요즘은 코테보다 출근해서 개발하고 외적으로 리액트 공부를 따라하고 있었는데 코드같은거를 더욱 이쁘게 짜게 되는 것 같다.