[파이썬] 백준 17822 : 원판 돌리기 (골드2)

[파이썬] 백준 17822 : 원판 돌리기 (골드2)

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

---

풀이

방향성 생각

• 원판을 2차원 격자로 나타내고 회전 구현을 위해서 큐로 구현하기.
  • 큐로 구현 안할거면, 리스트 하나 만들고 몇 번 회전했는지 관리하는 리스트도 같이 만들어서 관리하기기
• 연결된 숫자는 BFS로 구현하기

 

전체코드

from collections import deque
import sys

input = lambda : sys.stdin.readline().strip()
inside = lambda x,y : 0<=x<M and 0<=y<N
dires = [(1,0),(0,1),(-1,0),(0,-1)]

N,M,T = map(int,input().split())
arr = [deque(map(int,input().split())) for _ in range(N)]

# 현재 숫자에서 탐색하는 number와 같은 숫자 반환하기
def BFS(sx,sy,number):
    Q = deque([(sx,sy)])
    same_number = [(sx,sy)]
    V[sy][sx] = True
    while Q:
        x,y = Q.popleft()
        for dx,dy in dires:
            nx,ny = (x+dx)%M,y+dy # x는 환형이라 %M으로 맞춰주고, y는 그대로 관리해준다.
            if not inside(nx,ny):
                continue
            if not V[ny][nx] and arr[ny][nx] == number:
                V[ny][nx] = True
                Q.append((nx,ny))
                same_number.append((nx,ny))
    return same_number

for _ in range(T):

    # 회전하기
    x,d,k = map(int,input().split())
    for i in range(x,N+1,x):
        if d:
            arr[i-1].rotate(-k)
        else:
            arr[i-1].rotate(k)

    # BFS를 통해서 연결된 같은 숫자 관리하기. 같은 숫자 2개 이상인거만 remove list에 넣기
    V = [[False]*M for _ in range(N)]
    remove_lists = []
    for y in range(N):
        for x in range(M):
            if not V[y][x] and arr[y][x]:
                remove_list = BFS(x,y,arr[y][x])
                if len(remove_list) > 1:
                    remove_lists.extend(remove_list)

    # 제거할 숫자 있으면 제거하기
    if remove_lists:
        for rx,ry in remove_lists:
            arr[ry][rx] = 0

    # 제거할 숫자 없으면 평균 구해서 연산하기
    else:
        total = 0
        count = 0
        for y in range(N):
            for x in range(M):
                if arr[y][x]:
                    total += arr[y][x]
                    count += 1

        if count:
            avg = total/count

            for y in range(N):
                for x in range(M):
                    if arr[y][x]:
                        if arr[y][x] < avg:
                            arr[y][x] += 1
                        elif arr[y][x] > avg:
                            arr[y][x] -= 1

# 정답 구하기
answer = 0
for y in range(N):
    answer += sum(arr[y])
print(answer)

---

코멘트

• 예제 입력이 친절해서 쉬웠다.
• 0으로 나누는 예외만 생각했으면 됐을듯