난이도

Gold 5

풀이 참고 유무

X

막힌 부분

문제 설명이 애매모호함
-> 연합 결성~해제가 하루인지
당일에 연합이 여러개 있을 때 한번에 연산하는게 1일인지 헷갈림

문제

문제 바로가기

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
연합을 해체하고, 모든 국경선을 닫는다.
각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)
인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

예제 입력

2 20 50
50 30
20 40

예제 출력

1

문제 검토

연합 결성하는 것은 BFS가 유리해보인다.
나머지 조건들을 잘 구현하자.

풀이(python)

Python

from sys import stdin
from collections import deque

n,l,r = map(int,stdin.readline().split())
arr = [list(map(int,stdin.readline().split())) for _ in range(n)]
visited = [[0 for _ in range(n)] for _ in range(n)]

def BFS(row,col,visit):
    q=deque()
    q.append((row,col))
    dx=[0,1,-1,0]
    dy=[1,0,0,-1]
    #시작 국가 방문처리
    visited[row][col]=1-visit
    uni=[]
    #시작 국가를 연합에 넣음
    uni.append([arr[row][col],row,col])
    while q:        
        ro,co=q.popleft()
        #bfs로 탐색        
        for i in range(4):     
            nr=ro+dx[i]
            nc=co+dy[i]
            if nr<0 or nr>=n or nc<0 or nc>=n:
                continue
            #국가간의 인구수 차이가 l과 r사이고 방문하지 않았다면 연합에 넣어준다(국경선을 오픈함)
            a=abs(arr[nr][nc]-arr[ro][co])              
            if r>=a and a>=l and visited[nr][nc]==visit:
                uni.append([arr[nr][nc],nr,nc])
                q.append((nr,nc))
                visited[nr][nc]=1-visit                
            else:
                continue
    #연합을 리턴                     
    return uni
#연합의 인구 이동 함수
def move(uni):
    sum=0
    for x in range(len(uni)):
        sum+=uni[x][0]
    ag=sum//len(uni)
    for x in range(len(uni)):
        a,b=uni[x][1],uni[x][2]        
        arr[a][b]=ag
    return len(uni)
    
answer=0
mx=2
visit=1
#연합 수가 1이면 반복 종료(연합 없음)
while mx>1:
    visit=1-visit
    mx=0
    #연합의 모임리스트
    unis=list()
    for x in range(n):
        for y in range(n):
            if visited[x][y]==visit:
                #연합을 append해준다.        
                unis.append(BFS(x,y,visit))
    #국경선이 열려 그 날의 연합이 완성됐다면 인구이동 시작                
    for x in range(len(unis)):
        cnt=move(unis[x])
        if cnt>mx:
            mx=cnt
    #인구이동이 있었다면 카운트            
    if mx>1:
        answer+=1     
print(answer)    
     

1.BFS로 연합을 결성
2.그 날 연합을 모두 결성했다면 인구 이동 후 카운트
3.인구 이동이 없었다면 조건문을 나감

걸린 시간

1:05:00 (추정)

총평

완탐(BFS) 문제였다.
BFS는 어렵지 않지만 다른 과정들이 구현이 조금 까다로웠다.

아마 연합을 결성할 때마다 리스트를 추가하고 연합의 모임에 append하고 또 move()함수를 실행하는 과정에서 오버헤드가 많이 발생한 것 같다.

다른 풀이들을 보니 메모리와 시간을 더 줄일 수 있는 방법들이 존재하는 것 같다.

참고해서 나중에 다시 풀어보자.