1 minute read

문제

접근 방법

제한시간이 2초이고 n<=50, 최대 시간은 2000초보다 작게 데이터를 준다고 해서 완전탐색으로 하라는대로 구현하면 된다는 생각을 하였다. table을 다 순회해야 하므로 bfs를 사용하고자 하였다. 다음 방문할 곳과의 차이가 조건을 만족하면 deque에 저장하는 방법으로 bfs를 구현하였다. 이때 연합 구성 국가들 인구를 조정할 때 편하도록 조건을 만족하는 좌표들을 저장했다.

내가 이 문제에서 처음에 고려하지 못했던 것은 연합이 여러개가 있을 수 있다는 것이다. 예제를 꼼꼼하게 보는 습관을 길러야겠다.

정답 코드


import sys
from collections import deque
input = sys.stdin.readline

"""
50*50*2000 으로 해도 1억보다 작기에 문제 조건대로 해도 된다.

bfs를 하여 열릴 수 있다면 그 좌표와 그 나라 수를 저장
그 좌표들에 대해 인구 합 / 나라 수로 인구 update
"""

n,l,r = map(int, input().split())
maps = []
for _ in range(n):
    maps.append(list(map(int, input().split())))

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

#bfs를 한번 하면 하나의 연합을 구하는 것이다.
def bfs(start_y, start_x):
    q = deque()
    open = set()
    q.append((start_y, start_x))
    visited.add((start_y, start_x))
    open.add((start_y, start_x))
    while q:
        h,w = q.popleft()
        for dh,dw in moves:
            new_h, new_w = h+dh, w+dw
            if 0<=new_h<n and 0<=new_w<n and (new_h, new_w) not in visited:
                if l<=abs(maps[new_h][new_w] - maps[h][w])<=r:
                    open.add((new_h, new_w))
                    visited.add((new_h, new_w))
                    q.append((new_h, new_w))
    return open

days = 0
while True:
    total_open = []
    visited = set()
    for i in range(n):
        for j in range(n):
            if (i,j) in visited:
                continue
            open = bfs(i,j)
            if len(open) <= 1:
                continue
            else:
                total_open.append(open)
    if not total_open:
        break
    for o in total_open:
        total = 0
        num = 0
        for (i,j) in o:
            num+=1
            total += maps[i][j]
        replace = total // num
        for (i,j) in o:
            maps[i][j] = replace
    
    days += 1

print(days)

You May Also Enjoy