[BOJ] 16234 인구 이동_BFS

인구 이동

link

내 풀이

• 방식 : DFS, DP
• Pypy3

📰code

from collections import deque

N,L,R = list(map(int,input().split()))

A = []
for i in range(N):
    A += list(map(int,input().split()))

move = ((-1,0),(1,0),(0,-1),(0,1))
c = 0

while True :
    s = [[i,1] for i in A] # 연합의 합, 연합 지역의 수
    a = [-1 for _ in range(N*N)] # 연합 Map
    stopper = True 
    x,y = 0,0
    a[0] = 0
    q = deque()
    q.append((x,y))
    while q:
        x,y = q.popleft() # 시작좌표, 영역 구분
        u = a[x*N+y]
        for dx,dy in move:
            if 0<=x+dx<N and 0<=y+dy<N:
                mx,my = x+dx, y+dy
                if a[mx*N+my] == -1:
                    a[mx*N+my] = mx*N+my
                    q.append((mx,my))
                elif L<=abs(A[mx*N+my]-A[x*N+y])<=R: # 차이값이 L, R 사이인 경우
                    stopper = False
                    if u == a[mx*N+my]:
                        continue
                    else :
                        min_u, max_u = min(a[mx*N+my],u),max(a[mx*N+my],u)
                        s[min_u][0] += s[max_u][0]
                        s[min_u][1] += s[max_u][1]
                        s[max_u] = [0,0]
                        a = [min_u if i==max_u else i for i in a]
                        q.append((mx,my))
    if stopper:
        print(c)
        break
    else : c+=1
    A = [s[i][0]//s[i][1] if s[i][1]!=0 else 0 for i in a]

다른 풀이

• 방식 : DFS, DP

📰code

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

def bfs(c,A):
    x,y = c//N,c%N
    q = deque()
    q.append((x,y))
    popul = A[x*N+y]
    area = [x*N+y]
    while q:
        x,y = q.popleft() # 시작좌표, 영역 구분
        for dx,dy in move:
            if 0<=x+dx<N and 0<=y+dy<N :
                mx,my = x+dx, y+dy
                if L<=abs(A[mx*N+my]-A[x*N+y])<=R and visited[mx*N+my] != cnt:
                    visited[mx*N+my] = cnt
                    popul += A[mx*N+my]
                    area.append(mx*N+my)
                    q.append((mx,my))
    return area, popul

N,L,R = list(map(int,input().split()))

A = []
for i in range(N):
    A += list(map(int,input().split()))

move = ((-1,0),(1,0),(0,-1),(0,1))
visited = [-1 for _ in range(N*N)]
check = deque([(i) for i in range(N*N)])
cnt = 0
while True:
    for _ in range(len(check)):
        c = check.popleft()
        if visited[c] == cnt:
            continue
        visited[c] = cnt
        area,popul = bfs(c,A)
        if len(area)>1:
            popul = popul//len(area)
            for a in area:
                A[a]=popul
                check.append(a)
    if check:
        cnt +=1
    else :
        print(cnt)
        break

💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡