문제 설명

->링크<-

해결 방법

문제를 정확히 이해해야 하며 구현히 생각보다 복잡해서 잔실수때문에 시간을 많이 잡아먹었다.
본질만 보면 간단하다.

idea1. BFS로 연합국가끼리 묶어준다.

이때 탐색할때 같은 연합국끼리 하나씩 방문할때 미리 평균값을 구해준다.

idea2. 위방법을 활용해서 결괏값을 출력하기위한 실력이 필요하다

위 아이디어는 이렇다할 방식은 없고 단순히 구현실력과 관련있다.
1. 반복문을 원하는대로 활용하고 원하는 시점에 종료시킨다.
2. 실수가 없어야 된다.

위의 아이디어 2개만 확실히 숙지하면 충분히 해결할 수 있는 문제이다

해답 코드

import sys
from collections import deque
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
#매개변수로 받은 좌표에 인접한 국가의 차이가 조건에 맞지 않으면 True리턴
def sub(a,b):
  for d in range(4):
    newA = a + dy[d]
    newB = b + dx[d]
    if newA >= 0 and newA < N and newB >= 0 and newB < N:
      tmp = abs(matrix[a][b] - matrix[newA][newB])
      if tmp >= L and tmp <= R:
        return False
  return True
    
input = sys.stdin.readline
N, L, R = map(int, input().split())
matrix = []
for _ in range(N):
  matrix.append(list(map(int, input().split())))

res = 0
escape = 1
while escape > 0:
  # print(res,'번후 matrix!!!!')
  # for i in range(N):
  #   for j in range(N):
  #     print(matrix[i][j], end = ' ')
  #   print()
  # print('-------------------')
  #더이상 연합이 없다면 escape변수의 변화가 없음
  escape = 0
  #같은 연합들은 visit리스트 내에서 같은 숫자 처리
  visit = [[0] * N for _ in range(N)]
  #BFS로 visit에 같은 연합들 묵어주기
  for i in range(0,N):
    for j in range(0,N):
      #탐색하지 않았다면

      if visit[i][j] == 0:
        #주변에 인구차이가 조건만큼 나지 않는다면 -1처리
        if sub(i,j) == True:
          visit[i][j] = -1
        #아니라면 연합끼리 BFS로 visit리스트내에서 같은 숫자 처리 해주면서
        else:
          escape += 1
          #연합의 국가수를 저장할 변수 union_num
          union_num = 1
          Q = deque()
          Q.append((i,j))
          visit[i][j] = escape
          #연합 좌표가 저장될 리스트 union
          union = []
          union.append((i,j))
          #각 연합의 총 인구수가 저장될 변수 sum 
          sum = matrix[i][j]
          #현재 연합의 개수 합 좌표를 저장하기
          while Q:
            Y, X = Q.popleft()
            for d in range(4):
              newY = Y + dy[d]
              newX = X + dx[d]
              if newY >= 0 and newY < N and newX >= 0 and newX <N:
                tmp = abs(matrix[newY][newX]-matrix[Y][X])
                if tmp >= L and tmp <= R and visit[newY][newX] == 0:
                  Q.append((newY, newX))
                  visit[newY][newX] = visit[Y][X]
                  union.append((newY,newX))
                  union_num += 1
                  sum += matrix[newY][newX]
        
          #저장된 연합정보를 기반으로 인구 이동시켜주기
          avg = int(sum // union_num)

          for k in union:
            y, x = k
            matrix[y][x] = avg
  #1번이라도 인구 이동을 했다면
  if escape > 0:
    res += 1

print(res)

걸린시간

사실 난이도에 비해 시간을 많이 빼꼈다 하지만 그럴만도 한 문제이다 구현과정에서 복잡해지는 것을 피할 수 없었고 머리도 자연스럽게 같이 복잡해지니 잔실수가 생겼다 (중첩 for문에 같은 루프제어 변수를 사용해 버렸다.)