[백준_17822]원판 돌리기 with Python

백준(BOJ) "삼성 SW 역량 테스트 기출 문제" 문제집: 원판 돌리기(골드 3)

문제 출처: www.acmicpc.net/problem/17822

17822번: 원판 돌리기

 

1.알고리즘

• 초기 원판 데이터는 deque 데이터타입
• 입력되는 원판 회전 변수에 따라 회전
  • deque 데이터 타입의 rotate 함수를 사용하여 회전.(양수이면 시계방향, 음수이면 반시계방향)
• 인접 값 확인
  • 모든 원판의 모든 값을 대상으로 BFS 알고리즘을 사용한 함수를 통해 인접한 곳에 대상값을 갖는 곳이 있는지 확인
  • 값을 지워야하는 경우, is_adj 플래그를 True로 변경. 값을 지워야하는 곳을 0으로 변경
• is_adj 플래그가 False인 경우, 값 변경이 이루어지지 않았다는 의미
  • 원판을 1차원 리스트로 변경, 원판의 모든 값의 합과 원판의 0의 갯수를 연산
  • 원판의 수가 전부 0이 아닌 경우
    • 원판의 평균값 연산
    • 모든 원판의 0이 아닌 값을 평균값과 비교하여 +, - 연산
  • 원판의 수가 전부 0인 경우, 연산 종료.
• 회전 연산 종료 후 원판의 값의 총합 출력

 

2. 유의 사항

• 원판의 수가 모두 지워진 경우의 예외 처리
• 첫번째와 마지막 원판의 인접 원판 주의.
  • 1번째 원판은 2번째 원판과만 인접 / N번째 원판은 N-1번째 원판과만 인접
  • 1번째 원판과 N번째 원판은 인접하지 않음

 

3. 어려웠던 점, 해결 방법

 

4. 소스 코드

상세 코드 설명은 주석

import sys
from collections import deque
 
#BFS
def find_same_number(start, graph):
    route = deque([start])
    num = graph[start[0]][start[1]]
    visited = []
 
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while route:
        x, y = route.popleft()
 
        for idx in range(4):
            nx, ny = x + dx[idx], y + dy[idx]
 
            #원판 내에서의 값 설정. 마지막 값의 다음은 첫번째로, 첫번째 값의 앞은 마지막으로
            if ny == M:
                ny = 0
            if ny < 0:
                ny = M-1
 
            #원판 확인. 기준값과 원판의 값이 일치할 경우, 아직 확인하지 않은 위치의 값일 경우
            if 0<=nx<N and graph[nx][ny] == num and (nx, ny) not in visited:
                route.append((nx, ny))
                visited.append((nx, ny))
 
    return visited
 
 
if __name__=="__main__":
    N, M, T = map(int, sys.stdin.readline().split())
    round_plate = [deque(map(int, sys.stdin.readline().split())) for _ in range(N)]
 
    for _ in range(T):
        x, d, k = list(map(int, sys.stdin.readline().split()))
 
        #시계 방향, 반시계방향 설정
        d = 1 if d == 0 else -1
 
        #원판 회전(x부터 x만큼 증가하며 반복)
        for temp_x in range(x, N+1, x):
            round_plate[temp_x-1].rotate(d*k)
 
        #인접 값 확인
        is_adj = False
        for i in range(N):
            for j in range(M):
                if round_plate[i][j] == 0:
                    continue
                erase = find_same_number((i, j), round_plate)
                #지워야할 값이 존재할 경우
                if erase:
                    is_adj = True
                    for tx, ty in erase:
                        round_plate[tx][ty] = 0
                    #현재 비교 기준값도 변경
                    round_plate[i][j] = 0
 
        #인접하면서 같은 수가 없는 경우
        if not is_adj:
            round_plate_temp = sum(map(list, round_plate), [])
            sum_round_plate = sum(round_plate_temp)
 
            #원판에서 지운 값 갯수 확인
            zero_count = round_plate_temp.count(0)
            divide_num = N*M-zero_count
            #원판에 지워지지 않은 값이 있는 경우
            if divide_num != 0:
                adverage_round_plate = sum_round_plate/divide_num
 
                for i in range(N):
                    for j in range(M):
                        if round_plate[i][j] == 0:
                            continue
                        if round_plate[i][j] < adverage_round_plate:
                            round_plate[i][j] += 1
                        elif round_plate[i][j] > adverage_round_plate:
                            round_plate[i][j] -= 1
            
            #원판에 모든 값이 지워진 경우, 연산 종료
            else:
                break
 
    
    print(sum(sum(map(list, round_plate), [])))

 

 

5. 고민

• 인접값 확인 알고리즘,,,초기에 짰던 3~4개의 값 확인하는 알고리즘은 왜 통과를 못했을까