[BOJ] 17822번 원판 돌리기 (Python) [삼성 SW 역량 테스트 기출 문제]

문제

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

풀이

AC까지 1시간 15분 소요되었다.

• 삼성 문제는 항상 작은 문제 여러개가 합쳐져 있는 느낌이다. 문제를 꼼꼼하게 읽으면서 작은 문제들로 분해한 후 각개격파하자.

• 인접하는 예외처리에서 0~M을 벗어나는 경우를 음수만 고려했는데, M을 초과하는 경우에 대해서도 고려해줬어야 했다. python에서는 모듈로 연산으로 처리하는게 이런 두 경우가 자동으로 고려되어서 좋은 것 같다.

• zero division error 케이스를 잡지 못했다. 항상 나누기를 연산에서 사용할 때 분모가 혹시 0이 될 수 있는지 크로스체크하자.

• 완전탐색 DFS, BFS 코드 좀 더 손에 익어야 될 것 같다.

• BFS를 손코딩으로 거의 다 적고 코드를 작성하니 훨씬 좋았다. 어떤 변수를 어느 위치에 선언할지 어느정도 잡고 들어가니 혼란이 적었다.

from collections import deque

dx_dy = [(0,1),(0,-1),(1,0),(-1,0)]


def is_valid(x,y):
    """범위 안에 있는지"""
    if 0<=x<N and 0<=y<M:
        return True
    return False


def bfs(x, y, visited):
    target_num = maps[x][y] # None 아닌것만 전달됨
    queue = deque([(x, y)])
    near_x_y_list = [(x, y)]
    visited[x][y] = True

    while queue:
        now_x, now_y = queue.pop()
        for dx, dy in dx_dy:
            new_x, new_y = now_x + dx, now_y + dy
            if new_y < 0:  # 음수 처리
                new_y += M
            elif new_y >= M: # 초과 처리(!처음에 못찾음)
                new_y -= M

            if is_valid(new_x, new_y) and maps[new_x][new_y] \
                    and maps[new_x][new_y] == target_num and not visited[new_x][new_y]:
                visited[new_x][new_y] = True # 방문처리
                queue.append((new_x, new_y))
                near_x_y_list.append((new_x, new_y))

    return near_x_y_list


def rotate(x,d,k):
    """x의 배수인 원판을 d방향으로 k번 이동시키기"""
    for i in range(N):
        if ((i+1) % x) == 0:  # x의 배수번째
            for _ in range(k):
                if d == 0:  # 시계방향
                    maps[i].appendleft(maps[i].pop())
                else:  # 반시계 방향
                    maps[i].append(maps[i].popleft())


def rebalancing():
    """전체원판에 적힌 수 기준 평균에서 더하고 빼기"""
    valid_nums = []
    for i in range(N):
        for j in range(M):
            if maps[i][j]:  # None인건 제거된거
                valid_nums.append(maps[i][j])

    if len(valid_nums) == 0:
        return # 모두 None이면(!처음에 못찾음)

    avg = sum(valid_nums) / len(valid_nums)

    for i in range(N):
        for j in range(M):
            if maps[i][j]:  # None인건 제거된거
                if maps[i][j] > avg:
                    maps[i][j] -= 1
                elif maps[i][j] < avg:
                    maps[i][j] += 1


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


for x, d, k in x_d_k:  # O(50)
    # 1. x의 배수인 원판을 d방향으로 k번 이동시키기
    rotate(x, d, k)

    # 2. 원판에서 인접하면서 같은수 쭉 찾기
    total_near_x_y_list = []
    visited = [[False]*M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if maps[i][j] and not visited[i][j]:
                near_x_y_list = bfs(i, j, visited)
                # print(near_x_y_list)
                if len(near_x_y_list) >= 2:
                    total_near_x_y_list.append(near_x_y_list)

    # print(total_near_x_y_list)

    # 2-1. 인접하면서 같은 수 모두 지우기
    if len(total_near_x_y_list) >= 1:
        for near_x_y_list in total_near_x_y_list:
            for x, y in near_x_y_list:
                maps[x][y] = None
    else:  # 2-2. 인접하면서 같은 수 없으면 평균 구해서 평균기준 1더하고 빼기
        rebalancing()

    #print(total_near_x_y_list)
    #(maps)

sum = 0
for i in range(N):
    for j in range(M):
        if maps[i][j]:
            sum += maps[i][j]
print(sum)