[Python/Codetree] 토스트 계란틀

https://www.codetree.ai/training-field/frequent-problems/problems/toast-eggmold/submissions?page=1&pageSize=20&order=tier 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제

n * n개의 격자에 1 * 1 크기의 계란틀이 주어집니다.

각각의 계란틀에 담긴 계란의 양이 주어지며 계란틀은 정사각형 형태입니다. 계란틀을 이루는 4개의 선은 분리가 가능합니다.

계란틀이 있는 n * n 격자가 주어질 때 다음과 같은 규칙을 따릅니다.

• 계란의 양이 너무 차이나지 않게 하기 위해 하나의 선을 맞대고 있는 두 계란틀의 계란의 양의 차이가 L 이상 R 이하라면 계란틀의 해당 선을 분리합니다.
• 모든 계란틀에 대해 검사를 실시하고 위의 규칙에 해당하는 모든 계란틀의 선을 분리합니다.
• 선의 분리를 통해 합쳐진 계란틀의 계란은 하나로 합치고 이후에 다시 분리합니다.
• 합쳤다 다시 분리한 이후의 각 계란틀별 계란의 양은 (합쳐진 계란의 총 합)/(합쳐진 계란틀의 총 개수)가 됩니다. 편의상 소숫점은 버립니다.

예를 들어 아래 그림과 같이 계란틀의 계란의 양이 주어지고, 계란 이동의 범위가 15 이상 24 이하로 주어진다면,

아래 그림과 같이 계란틀의 선을 분리하게 됩니다.

계란이 모두 합쳐지고 난 뒤 계란의 양은 아래 그림과 같이 바뀌게 됩니다.

위의 과정이 한 번의 계란의 이동이며, 계란의 이동이 더 이상 필요 없을 때까지 해당 과정을 반복합니다.

n * n 격자의 계란틀에 있는 계란의 양이 주어질 때, 계란의 이동이 몇 번 일어나는지를 구하는 프로그램을 작성하세요.

입력 형식

첫번째 줄에 총 칸의 크기 n, 계란 이동의 범위의 최솟값 L, 계란 이동 범위의 최댓값 R을 공백을 두고 출력합니다.

두번째 줄부터 (n+1)번째 줄까지 각 칸의 계란의 양이 공백을 사이에 두고 주어집니다.

• 1 ≤ n ≤ 50
• 1 ≤ L ≤ R ≤ 100
• 0 ≤ (각 칸의 계란의 양) ≤ 100
• 계란의 이동이 발생하는 총 횟수는 2000번보다 작다고 가정해도 좋습니다.

출력 형식

계란의 이동이 일어난 총 횟수를 출력하세요.

풀이

Code

from collections import deque

# 1. BFS 함수 생성
def bfs(x, y) :
    global state
    # 1-1. 큐에 현재 인덱스 삽입
    queue = deque()
    queue.append((x, y))
    # 1-2. 현재 위치 방문 처리
    visited[x][y] = True
    # 1-3.
    sum_index = [(x, y)]
    # 1-4.
    while queue :
        # 1-4-1. 위치 인덱스 반환
        x, y = queue.popleft()
        # 1-4-2.
        for dir_x, dir_y in [(-1, 0), (1, 0), (0, -1), (0, 1)] :
            nx, ny = x + dir_x, y + dir_y
            # 예외 처리
            if nx < 0 or nx >= n or ny < 0 or ny >= n : continue
            # 다음 위치에 방문하지 않은 경우
            if not visited[nx][ny] :
                # 계란 양의 차이가 범위 안에 들 경우
                if L <= abs(graph[x][y] - graph[nx][ny]) <= R :
                    # 방문 처리
                    visited[nx][ny] = True
                    # 계란틀이 분리되어 합쳐지는 인덱스 리스트에 현재 위치 삽입
                    sum_index.append((nx, ny))
                    # 큐에 다음 위치 삽입
                    queue.append((nx, ny))
    # 1-5. 인덱스 리스트의 길이가 1보다 클 경우
    if len(sum_index) > 1 :
        if state : state = False
        # 계란 양 재배치
        div = sum([graph[x][y] for x, y in sum_index]) // len(sum_index)
        for x, y in sum_index :
            graph[x][y] = div
    return 

n, L, R = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
# 2. 카운트 변수 생성
cnt = 0
# 3.
while True :
    # 3-1. 방문 여부 리스트 생성
    visited = [[False for _ in range(n)] for _ in range(n)]
    state = True
    # 3-2.
    for i in range(n) :
        for j in range(n) :
            # 해당 위치에 방문하지 않은 경우
            if not visited[i][j] :
                # BFS 실행
                bfs(i, j)
    # 3-3. 계란틀의 변동이 있는 경우
    if not state : cnt += 1
    # 3-4. 변동이 없을 경우
    else : break # 탈출
# 4. 결과 출력
print(cnt)