[파이썬] 백준 16234 : 인구이동 (골드4)

[파이썬] 백준 16234 : 인구이동 (골드4)

16234번: 인구 이동

---

문제

---

풀이

0. 방향성 생각

• BFS로 군집 구하기.
•  

1. 입력

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

n,low,high = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]

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

• 입력 전부 받아준다.
• 이동방향 4방향 정의.

2. BFS 함수 정의

def bfs(x,y,array):
    federation,population,count = [(x,y)],array[y][x],1
    q = deque([(x,y)])
    visit[y][x] = True
    while q:
        x,y = q.popleft()

        for dx,dy in step:
            nx = x + dx
            ny = y + dy
            if 0<=nx<n and 0<=ny<n and not visit[ny][nx]:
                if low <= abs(array[ny][nx]-array[y][x])<= high:
                    q.append((nx,ny))
                    visit[ny][nx] = True
                    population += array[ny][nx]
                    federation.append((nx,ny))
                    count += 1
    return federation,population,count

• before 입력 받아서 연합 좌표, 총 인구수, 좌표 개수 반환

 

3. 출력

before = [row[:] for row in arr]
answer = 0
while True:
    
    after = [row[:] for row in before]
    visit = [[False]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if not visit[i][j]:
                f,p,c = bfs(j,i,before)
                np = p//c
                for x,y in f:
                    after[y][x] = np
    
    if before != after:
        answer += 1
        before = [row[:] for row in after]
    else:
        print(answer)
        break

• before 처음에 복사해놓는다.
• after는 before 또 복사한다.
• visit 방문처리 False 초기화.
• 탐색 안했으면 BFS 돌린다. 좌표 f에 값을 np로 바꾼다.
• 전,후 차이가 있으면 answer += 1, before 업데이트. 아닌 경우 answer 출력 후 탈출

 

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

n,low,high = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]

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

def bfs(x,y,array):
    federation,population,count = [(x,y)],array[y][x],1
    q = deque([(x,y)])
    visit[y][x] = True
    while q:
        x,y = q.popleft()

        for dx,dy in step:
            nx = x + dx
            ny = y + dy
            if 0<=nx<n and 0<=ny<n and not visit[ny][nx]:
                if low <= abs(array[ny][nx]-array[y][x])<= high:
                    q.append((nx,ny))
                    visit[ny][nx] = True
                    population += array[ny][nx]
                    federation.append((nx,ny))
                    count += 1
    return federation,population,count

before = [row[:] for row in arr]
answer = 0
while True:
    
    after = [row[:] for row in before]
    visit = [[False]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if not visit[i][j]:
                f,p,c = bfs(j,i,before)
                np = p//c
                for x,y in f:
                    after[y][x] = np
    
    if before != after:
        answer += 1
        before = [row[:] for row in after]
    else:
        print(answer)
        break

 

코멘트

웰노운은 쉽다