백준 원판 돌리기 [17822] 파이썬(Python) 코드 + 해설

백준 17822 원판 돌리기 문제

 

문제 설명

반지름이 1부터 N까지인 원판들이 바닥에 놓여 있고, 각 원판에는 M개의 정수가 적혀 있다. 원판들은 중심을 공유하며, 각 원판의 번호는 작은 것부터 큰 것까지 1부터 N까지이다. 각 원판의 위치는 (i,j)로 표현되며, i는 원판의 번호, j는 원판 위의 숫자 위치이다.
원판들은 독립적으로 회전할 수 있으며, 회전은 시계 방향 또는 반시계 방향으로 이루어진다. 회전 후에는 다음과 같은 작업을 수행한다:

1. 인접하면서 수가 같은 것들을 모두 찾는다.
   • 인접한 위치는 다음과 같다:
     • 같은 원판에서 양 옆에 있는 숫자들
     • 같은 위치의 위아래 원판 숫자들
2. 인접하면서 수가 같은 것이 있으면, 해당 수들을 지운다 (0으로 만든다).
3. 없으면, 원판에 적힌 수들의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

이 작업을 T번 수행한 후 원판에 적힌 수의 합을 구하는 것이 목표이다.

입력 및 출력

• 입력:
  • 첫째 줄: N,M,T(2≤N, M≤50, 1≤T≤50)
  • 둘째 줄부터 N개의 줄: 각 원판에 적힌 M개의 정수 (1≤정수≤1000)
  • 다음 T개의 줄: xi​,di​,ki​
    • xi: 회전할 원판의 배수 번호 (2≤xi≤N)
    • di​: 회전 방향 (0: 시계 방향, 1: 반시계 방향)
    • ki​: 회전할 칸의 수 (1≤ki<M)
• 출력:
  • 원판을 T번 회전시킨 후 원판에 적힌 수의 합

문제 접근

• 데이터 구조:
  • 원판들을 2차원 리스트로 표현한다. 각 원판은 길이 M의 리스트로, 총 N개의 원판이 있다.
• 회전 구현:
  • 주어진 명령에 따라 해당하는 원판들을 회전시킨다.
  • 회전 방향에 따라 리스트를 회전시킨다.
• 인접한 수 탐색 및 제거:
  • 각 숫자 위치에 대해 인접한 위치를 검사하여 같은 수를 찾는다.
  • 같은 수가 있으면 해당 위치를 기록해둔다.
  • 모든 탐색이 끝난 후 기록된 위치의 수들을 제거한다 (0으로 만든다).
• 평균 계산 및 수 조정:
  • 인접한 수를 제거한 후, 만약 제거된 수가 없다면 평균을 계산한다.
  • 평균보다 큰 수는 1을 빼고, 작은 수는 1을 더한다 (0인 수는 제외).

알고리즘 구현

1. 입력 및 초기화

import sys
input = sys.stdin.readline

N, M, T = map(int, input().split())
circles = [list(map(int, input().split())) for _ in range(N)]
commands = [tuple(map(int, input().split())) for _ in range(T)]

 

• circles: 원판들의 상태를 저장하는 리스트
• commands: 회전 명령들을 저장하는 리스트

2. 회전 함수 구현

def rotate(circle_idx, direction, k):
    if direction == 0:  # 시계 방향
        circles[circle_idx] = circles[circle_idx][-k:] + circles[circle_idx][:-k]
    else:  # 반시계 방향
        circles[circle_idx] = circles[circle_idx][k:] + circles[circle_idx][:k]

• circle_idx: 회전할 원판의 인덱스
• direction: 회전 방향 (0: 시계 방향, 1: 반시계 방향)
• k: 회전할 칸의 수

3. 인접한 수 제거 함수 구현

def remove_adjacent():
    has_same = False
    to_remove = [[False]*M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if circles[i][j] == 0:
                continue
            current = circles[i][j]
            # 현재 위치와 인접한 위치 검사
            adjacent_positions = []
            # 같은 원판에서의 왼쪽과 오른쪽 검사
            left = (j - 1) % M
            right = (j + 1) % M
            if circles[i][left] == current:
                to_remove[i][j] = to_remove[i][left] = True
                has_same = True
            if circles[i][right] == current:
                to_remove[i][j] = to_remove[i][right] = True
                has_same = True
            # 위아래 원판 검사
            if i > 0 and circles[i-1][j] == current:
                to_remove[i][j] = to_remove[i-1][j] = True
                has_same = True
            if i < N -1 and circles[i+1][j] == current:
                to_remove[i][j] = to_remove[i+1][j] = True
                has_same = True
    # 제거 수행
    for i in range(N):
        for j in range(M):
            if to_remove[i][j]:
                circles[i][j] = 0
    return has_same

• has_same: 인접하면서 같은 수가 있는지 여부를 반환한다.

4. 평균 계산 및 수 조정 함수 구현

def adjust_numbers():
    total = 0
    count = 0
    for i in range(N):
        for j in range(M):
            if circles[i][j] != 0:
                total += circles[i][j]
                count += 1
    if count == 0:
        return
    average = total / count
    for i in range(N):
        for j in range(M):
            if circles[i][j] != 0:
                if circles[i][j] > average:
                    circles[i][j] -= 1
                elif circles[i][j] < average:
                    circles[i][j] += 1

5. 시뮬레이션 진행

for x, d, k in commands:
    # 회전
    for i in range(N):
        if (i + 1) % x == 0:
            rotate(i, d, k)
    # 인접한 수 제거
    if not remove_adjacent():
        adjust_numbers()

6. 결과 출력

result = sum(map(sum, circles))
print(result)

백준 17822 원판 돌리기 파이썬(Python) 정답 코드

import sys
input = sys.stdin.readline

N, M, T = map(int, input().split())
circles = [list(map(int, input().split())) for _ in range(N)]
commands = [tuple(map(int, input().split())) for _ in range(T)]

def rotate(circle_idx, direction, k):
    if direction == 0:  # 시계 방향
        circles[circle_idx] = circles[circle_idx][-k:] + circles[circle_idx][:-k]
    else:  # 반시계 방향
        circles[circle_idx] = circles[circle_idx][k:] + circles[circle_idx][:k]

def remove_adjacent():
    has_same = False
    to_remove = [[False]*M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if circles[i][j] == 0:
                continue
            current = circles[i][j]
            # 같은 원판에서의 왼쪽과 오른쪽 검사
            left = (j - 1) % M
            right = (j + 1) % M
            if circles[i][left] == current:
                to_remove[i][j] = to_remove[i][left] = True
                has_same = True
            if circles[i][right] == current:
                to_remove[i][j] = to_remove[i][right] = True
                has_same = True
            # 위아래 원판 검사
            if i > 0 and circles[i-1][j] == current:
                to_remove[i][j] = to_remove[i-1][j] = True
                has_same = True
            if i < N -1 and circles[i+1][j] == current:
                to_remove[i][j] = to_remove[i+1][j] = True
                has_same = True
    # 제거 수행
    for i in range(N):
        for j in range(M):
            if to_remove[i][j]:
                circles[i][j] = 0
    return has_same

def adjust_numbers():
    total = 0
    count = 0
    for i in range(N):
        for j in range(M):
            if circles[i][j] != 0:
                total += circles[i][j]
                count += 1
    if count == 0:
        return
    average = total / count
    for i in range(N):
        for j in range(M):
            if circles[i][j] != 0:
                if circles[i][j] > average:
                    circles[i][j] -= 1
                elif circles[i][j] < average:
                    circles[i][j] += 1

for x, d, k in commands:
    # 회전
    for i in range(N):
        if (i + 1) % x == 0:
            rotate(i, d, k % M)  # k가 M 이상일 수 있으므로 M으로 나눈 나머지로 회전
    # 인접한 수 제거
    if not remove_adjacent():
        adjust_numbers()

result = sum(map(sum, circles))
print(result)

 

백준 17822 원판 돌리기 문제 제출 결과

 

백준 17822 문제 제출 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다.