[백준 17822][Python] 원판 돌리기

www.acmicpc.net/problem/17822

17822번: 원판 돌리기

Logic

erase_set: 원판에서 지울 좌표를 저장하는 Set -> 중복 제거를 위해서!

checkHorizontal(num): 원판의 가로라인에서 인접하면서 수가 같은 경우를 찾아서 erase_set에 저장한다.

checkVertical(num): 원판의 세로라인에서 인접하면서 수가 같은 경우를 찾아서 erase_set에 저장한다.

processAverage(): 원판 점수의 평균을 구하고, 평균보다 큰 점수는 -1, 평균보다 작은 점수는 +1해준다.

rotate(num, dir, k): num번째 원판을 dir방향으로 k번 회전하는 함수

 

1. T만큼 while문을 돌면서 각 원판 회전 정보를 받아온다.

2. 원판 회전 정보에서 x의 배수인 원판을 d방향으로(시계 or 반시계) k만큼 회전시킨다. -> rotate()함수에서

3. 회전이 완료되면, 원판에서 지울 좌표를 erase_set에 저장한다.

   for i in range(1, N+1):
       checkHorizontal(i)
   
   for i in range(M):
       checkVertical(i)

4. erase_set을 list로 변환하여 erase_list에 저장한다.

   4-1. erase_list에 원소가 하나도 없다면, 원판에서 지울 게 없다는 뜻이므로 processAverage()함수를 실행한다.

   4-2. erase_list에 있는 원소들을 모두 지워준다.

5. 원판의 점수를 모두 더해서 circle_sum에 저장한다. circle_sum이 0이라면 더 이상 반복해도 똑같은 결과가 나오기 때문에 while문을 빠져나온다.

Review

• 걸린시간: 1시간 40분

• 실수한 부분

  while x <= N:
      circle[x] = rotate(x, d, k)
      x += x

  x의 배수인 원판을 while문을 돌면서 rotate 하였는데, x+=x로 하게 되면 x가 계속 더해져서 틀리게 된다. tmp에 x를 담아두고 이 tmp를 계속 더해주어야 한다..

  사소한 실수로 시간이 오래 걸리니 주의하자 ㅠㅠ

Code

def checkHorizontal(num):
    global erase_set
    for j in range(M-1):
        if circle[num][j] == 0:
            continue
        if circle[num][j] == circle[num][j+1]:
            erase_set.add((num, j))
            erase_set.add((num, j+1))
    if circle[num][M-1] != 0 and circle[num][M-1] == circle[num][0]:
        erase_set.add((num, M-1))
        erase_set.add((num, 0))

def checkVertical(num):
    global erase_set
    for j in range(1, N):
        if circle[j][num] == 0:
            continue
        if circle[j][num] == circle[j+1][num]:
            erase_set.add((j, num))
            erase_set.add((j+1, num))

def rotate(num, dir, k):
    k %= len(circle[num])
    if dir == 0: #시계방향
        left = circle[num][:-k]
        right = circle[num][-k:]
        return right + left
    else: #반시계방향
        left = circle[num][:k]
        right = circle[num][k:]
        return right + left

def processAverage():
    Sum = 0
    Cnt = 0
    for i in range(1, N+1):
        for j in range(M):
            if(circle[i][j] == 0):
                continue
            Sum += circle[i][j]
            Cnt += 1

    Average = Sum / Cnt
    for i in range(1, N+1):
        for j in range(M):
            if(circle[i][j] == 0):
                continue
            if(circle[i][j] > Average):
                circle[i][j] -= 1
            elif(circle[i][j] < Average):
                circle[i][j] += 1

N, M, T = map(int, input().split())
circle = [[] for y in range(N+1)]

for i in range(1, N+1):
    circle[i] = [int(x) for x in input().split()]


circle_sum = 0
cnt = 0

while cnt < T:
    x, d, k = map(int, input().split())
    tmp = x
    while x <= N:
        circle[x] = rotate(x, d, k)
        x += tmp

    erase_set = set()

    for i in range(1, N+1):
        checkHorizontal(i)

    for i in range(M):
        checkVertical(i)

    erase_list = list(erase_set)
    if(len(erase_list) == 0):
        processAverage()
    else:
        for item in erase_list:
            circle[item[0]][item[1]] = 0

    circle_sum = 0
    for i in range(1, N+1):
        for j in range(M):
            circle_sum += circle[i][j]

    if circle_sum == 0:
        break
    cnt += 1

print(int(circle_sum))