132. [삼성기출28]Python 백준 17822 번 원판 돌리기

안녕하세요 코딩하는 덕구입니다.

백준 17822 원판돌리기 입니다.

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

17822번: 원판 돌리기

 

백준 17822 원판돌리기 정답코드 입니다. 설명은 아래에 있습니다.

 

from collections import deque
N, M, T = map(int, input().split())
circle_num = [[]] + [deque(map(int, input().split())) for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def rotate(x, d, k):
    for i in range(2, N+1):#회전
        if i % x == 0:
            if d == 0: #시계방향으로 k번 회전
                for _ in range(k):
                    tmp = circle_num[i].pop()
                    circle_num[i].appendleft(tmp)

            else: #반시계방향으로 K번 회전
                for _ in range(k):
                    tmp = circle_num[i].popleft()
                    circle_num[i].append(tmp)

def adj_del():
    del_list = []
    deleted = [[False for _ in range(M)] for _ in range(N + 1)]
    for x in range(1, N + 1):
        for y in range(M):
            if circle_num[x][y] != 'x':
                for i in range(4):
                    nx = x + dx[i]
                    ny = (y + dy[i]) % M
                    if 1 <= nx <= N and 0 <= ny < M:
                        if circle_num[x][y] == circle_num[nx][ny]:
                            if not deleted[x][y]:
                                deleted[x][y] = True
                                del_list.append([x, y])
                            if not deleted[nx][ny]:
                                deleted[nx][ny] = True
                                del_list.append([nx, ny])

    for d in del_list:
        x, y = d
        circle_num[x][y] = 'x'

    if del_list:
        return True
    return False

def cal():
    global g_total
    tmp = 0
    total = 0
    to_visit = []
    for i in range(1, N + 1):
        for j in range(M):
            if circle_num[i][j] != 'x':
                total += 1
                tmp += circle_num[i][j]
                to_visit.append([i, j])
    if total == 0:
        return
    g_total = total
    tmp = tmp/total
    for t in to_visit:
        x, y = t
        if circle_num[x][y] > tmp:
            circle_num[x][y] -= 1

        elif circle_num[x][y] < tmp:
            circle_num[x][y] += 1

g_total = N*M
for t in range(T):
    x, d, k = map(int, input().split())
    rotate(x, d, k)

    if g_total != 0:
        if not adj_del():
            cal()

ans = 0
for i in range(1, N + 1):
    for j in range(M):
        if circle_num[i][j] != 'x':
            ans += circle_num[i][j]

print(ans)

 

문제 접근

핵심적으로 2 가지를 구현해야됩니다.

 

1. 회전가능한 원판

회전가능한 원판은 deque 으로 쉽게 구현 가능합니다.

오른쪽으로 한칸 회전이라면 

deque의 맨 뒤에 있는 성분을 pop 한 후 해당 성분을 맨 앞에 넣어주면 됩니다.

[1, 2, 3, 4] -> [4, 1, 2, 3]

왼쪽으로 한칸 회전이라면

deque의 맨 앞 성분을 맨 뒤로 옮겨주면 됩니다.

[1, 2, 3, 4] -> [2, 3, 4, 1]

 

2. 원판의 인접한 숫자 탐색

인접한 숫자는 그래프 탐색처럼 상하좌우를 탐색하면 됩니다.

다만 원판의 가장 마지막부분과 첫 부분도 인접하므로

다음과 같이 좌표가 넘어간다면 첫 번째 좌표가 되도록 보정해주면 됩니다.

ny = (y + dy[i]) % M

 

Python 코드 구현

먼저 구현에 필요한 라이브러리를 가져온 후 변수들을 입력받습니다.

dx, dy는 인접한 숫자를 탐색할 때 씁니다.

from collections import deque
N, M, T = map(int, input().split())
circle_num = [[]] + [deque(map(int, input().split())) for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

 

남아있는 성분의 개수 g_total을 선언합니다.

T번 동안 반복하며,

입력대로 회전합니다. rotate(x, d, k)

원판에 숫자가 남아있다면 인접한 숫자는 삭제합니다. if g_total != 0: adj_del():

인접한 숫자가 없다면 if not adj_del(): 평균을 구해 남아있는 숫자를 보정합니다.cal()

g_total = N*M
for t in range(T):
    x, d, k = map(int, input().split())
    rotate(x, d, k)

    if g_total != 0:
        if not adj_del():
            cal()

 

회전이 끝나면 남아있는 수를 모두 더해 출력합니다.

ans = 0
for i in range(1, N + 1):
    for j in range(M):
        if circle_num[i][j] != 'x':
            ans += circle_num[i][j]
print(ans)

 

원판의 회전입니다. 회전 방향이 시계방항이면 맨 뒤의 성분을 맨 앞으로 옮깁니다.

방향이 반대라면 맨 앞의 성분을 맨 뒤로 옮깁니다.

def rotate(x, d, k):
    for i in range(2, N+1):#회전
        if i % x == 0:
            if d == 0: #시계방향으로 k번 회전
                for _ in range(k):
                    tmp = circle_num[i].pop()
                    circle_num[i].appendleft(tmp)

            else: #반시계방향으로 K번 회전
                for _ in range(k):
                    tmp = circle_num[i].popleft()
                    circle_num[i].append(tmp)

 

인접한 성분을 삭제합니다. 모든 원판을 탐색하면서 인접한 숫자가 있다면 del_list에 추가한 후

del_list안에 있는 좌표들의 숫자를 모두 삭제합니다.

만약 지울게 없다면 False를 return

있다면 True를 return 합니다.

def adj_del():
    del_list = []
    deleted = [[False for _ in range(M)] for _ in range(N + 1)]
    for x in range(1, N + 1):
        for y in range(M):
            if circle_num[x][y] != 'x':
                for i in range(4):
                    nx = x + dx[i]
                    ny = (y + dy[i]) % M
                    if 1 <= nx <= N and 0 <= ny < M:
                        if circle_num[x][y] == circle_num[nx][ny]:
                            if not deleted[x][y]:
                                deleted[x][y] = True
                                del_list.append([x, y])
                            if not deleted[nx][ny]:
                                deleted[nx][ny] = True
                                del_list.append([nx, ny])

    for d in del_list:
        x, y = d
        circle_num[x][y] = 'x'

    if del_list:
        return True
    return False

 

숫자를 보정해주는 cal입니다.

만약 삭제되지 않은 숫자라면 다시 방문할 리스트에 추가한 후 

추후에 리스트를 순회하며 조건에 맞게 숫자를 보정해줍니다.

def cal():
    global g_total
    tmp = 0
    total = 0
    to_visit = []
    for i in range(1, N + 1):
        for j in range(M):
            if circle_num[i][j] != 'x':
                total += 1
                tmp += circle_num[i][j]
                to_visit.append([i, j])
    if total == 0:
        return

    g_total = total
    tmp = tmp/total
    for t in to_visit:
        x, y = t
        if circle_num[x][y] > tmp:
            circle_num[x][y] -= 1

        elif circle_num[x][y] < tmp:
            circle_num[x][y] += 1

 

백준 17822 원판돌리기 Python 코드였습니다.

감사합니다.