[BOJ] 16234번 인구 이동 / 사용언어 : 파이썬(python)

※ 문제링크 

16234번: 인구 이동

해당문제는 BFS의 개념을 활용하여 사방위를 확인하고, 반복문을 통해 가능한 인구이동의 경우의 수를 체크하여 풀 수 있는 문제로, BFS의 기본적인 개념만 이해하고 있으면 통과는 생각보다 쉽게 가능했다. 다만, 단순한 반복문과 BFS의 조합으로 문제를 해결하면Pypy3로만 통과 가능하였고, Python3로 해결하기 위해서는 반복문을 반복할때 완전탐색을 하는 것이 아니라 이전의 결과값에 따라다르게 탐색을 하는 방식으로 구현해야하는 문제였다. 첫번째 해결방안은 금방 떠올려 해결하였으나 두번째 해결방안은 혼자서 해결하는 것이 불가능하여 백준에서 코드를 공개해주신 다른분의 코드를 보며 학습하는 방식으로 문제를 해결하였다.

자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 바탕으로 변수와 행렬을 작성해준다.

2. BFS를 활용하여 사방위를 탐색할 수 있게하고, 방문여부를 확인할 2차원 배열과 인구이동여부를 체크할 변수를 작성하고, 반복문을 통해 인구이동이 일어날 좌표값들의 집합을 확인한 이후, 인구이동이 발생한 이후의 인구값을 구하여 해당 좌표들의 값을 변경해줄함수를 작성한다. (함수 작성시 이전에 탐색 좌표값들을 제외할 수 있게 변형한 후 탐색을 하게끔 작성하면 Python3로 통과가능)

3. 2번에서 작성한 함수들 반복문을 통해 반복하고, 인구이동이 일어나지 않으면 반복문을 종료한 이후 인구이동 날짜를 출력해준다.(+시간 및 메모리 절감을 위해 sys를 사용하였습니다.)

 

# Pypy3로만 통과가능

from collections import deque
import sys

# input = sys.stdin.readline
N, L, R = map(int, input().split()) # N: 행렬의 크기 / L: 최솟값 / R: 최댓값
field = [list(map(int, input().split())) for _ in range(N)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs():
    queue = deque()
    circulation_cp = False
    visited = [[False for _ in range(N)] for _ in range(N)]

    for cp_x in range(N):
        for cp_y in range(N):
            cps_loc = [[cp_x, cp_y]]
            cps_ans = field[cp_y][cp_x]
            if visited[cp_y][cp_x] == False:
                queue.append([cp_x, cp_y])
                visited[cp_y][cp_x] = True
                while queue:
                    x, y = queue.popleft()
                    for i in range(4):
                        nx = x + dx[i]
                        ny = y + dy[i]
                        if 0 <= nx < N and 0 <= ny < N:
                            check = abs(field[y][x] - field[ny][nx])
                            if L <= check <= R and visited[ny][nx] == False:
                                 if circulation_cp == False:
                                     circulation_cp = True
                                 visited[ny][nx] = True
                                 queue.append([nx, ny])
                                 cps_loc.append([nx, ny])
                                 cps_ans += field[ny][nx]
                if len(cps_loc ) > 1:
                    new_pop = cps_ans // len(cps_loc)
                    for x, y in cps_loc:
                        field[y][x] = new_pop
    return circulation_cp

ans = 0
while bfs():
    ans += 1
print(ans)

 

# 코드참조 : https://www.acmicpc.net/source/41668871
# Python3 해결

from collections import deque
import sys

# input = sys.stdin.readline
N, L, R = map(int, input().split()) # N: 행렬의 크기 / L: 최솟값 / R: 최댓값
field = [list(map(int, input().split())) for _ in range(N)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

visited = [[0 for _ in range(N)] for _ in range(N)]
queue1 = deque()
for cp_x in range(N):
    for cp_y in range(N):
        queue1.append([cp_x, cp_y])

def bfs():
    global cp
    while True:
        for _ in range(len(queue1)):
            cp_x, cp_y = queue1.popleft()
            if visited[cp_y][cp_x] == cp:
                continue
            queue2 = deque()
            queue2.append([cp_x, cp_y])
            cps_loc = [[cp_x, cp_y]]
            cps_ans = field[cp_y][cp_x]
            visited[cp_y][cp_x] = cp
            while queue2:
                x, y = queue2.popleft()
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx < N and 0 <= ny < N and visited[ny][nx] != cp:
                        check = abs(field[y][x] - field[ny][nx])
                        if L <= check <= R:
                            visited[ny][nx] = cp
                            queue2.append([nx, ny])
                            cps_loc.append([nx, ny])
                            cps_ans += field[ny][nx]
            if len(cps_loc) > 1:
                new_pop = cps_ans // len(cps_loc)
                for x, y in cps_loc:
                    field[y][x] = new_pop
                    queue1.append([x, y])
        if queue1:
            cp += 1
        else:
            return

cp = 1
bfs()
print(cp-1)

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.