[CT] 토스트 계란틀

1. 문제

• n * n 격자에 담긴 1 * 1의 계란틀

  • 정사각형 모양 계란틀에 담긴 계란의 양 제공
  • 계란틀을 이루는 4개의 선은 분리 가능

• 규칙

  1. 계란의 양이 너무 차이나지 않게 하기 위해 하나의 선을 맞대고 있는 두 계란틀의 양의 차이가 L이상 R이하라면 계란틀의 해당 선 분리

  2. 모든 계란틀에 대해 검사 실시, 1 규칙에 해당하는 모든 계란틀의 선 분리

  3. 선의 분리를 통해 합쳐진 계란틀의 계란은 하나로 합치고 이후에 다시 분리

  4. 합쳤다 다시 분리한 이후의 계란틀 별 계란의 양은 (합쳐진 계란 총 합)/(합쳐진 계란틀 수), 편의상 소수점 버림

     

  • 위 과정이 1번의 계란 이동이며, 더 이상 이동이 필요 없을 때까지 과정 반복

    ⇒ n*n 격자의 계란 틀에 있는 계란의 양 주어질 때, 계란의 이동이 몇 번 일어나는지 출력

2. 풀이

• BFS!
  • 더이상 계란의 이동이 일어나지 않을 때까지 이동할 계란이 있는 칸을 찾고 계란을 이동하기 (반복문)
    • 이 때 이동할 계란이 있는 칸을 찾기 위해 매 탐색마다 격자의 각 칸의 방문 여부를 확인하며, 방문하지 않은 칸은 BFS를 통해서 주변에 계란틀의 양의 차이가 L이상 R이하인 칸들을 모두 찾아 group변수에 저장한다
    • 탐색이 끝난 후 group의 길이가 2이상이면 (==BFS탐색을 시작한 칸 주변에 계란을 이동할 칸이 존재한다면) 해당 계란들을 이동시킨다.
  • 만약 전체 격자에 대해 탐색 후에 계란이 이동했다면 결과 변수 answer += 1하며, 탐색을 했음에도 이동할 계란이 아예 없었다면 반복문을 중단시키고 결과를 출력한다

3. 코드

from collections import deque
n, L, R = map(int, input().split())
eggs = [ list(map(int, input().split())) for _ in range(n)]
answer = 0

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]

def bfs(r, c):
    group = [(r,c)]
    queue = deque()
    queue.append((r,c))
    
    while queue:
        cr, cc = queue.popleft()
        for i in range(4):
            nr = cr + dr[i]
            nc = cc + dc[i]
            
            if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
                if L <= abs(eggs[nr][nc] - eggs[cr][cc]) <= R: 
                    visited[nr][nc] = True
                    group.append((nr, nc))
                    queue.append((nr, nc))
    return group 

while True:
    # find groups that have L < diff < R
    stop = True
    visited = [[False for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:                
                visited[i][j] = True
                group = bfs(i, j)
                
                if len(group) > 1:
                    stop = False
                    egg = sum([eggs[r][c] for r,c in group]) // len(group)
                    for r, c in group:
                        eggs[r][c] = egg
    if stop:
        break
  
    answer += 1
    
print(answer)

+α

• 유사/동일 문제 : 백준 #16234 인구이동