123. [삼성기출19]Python 백준 16234 번 인구 이동 자세한 설명

안녕하세요 코딩하는 덕구입니다.

백준 16234 번 인구 이동 입니다.

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

 

먼저 백준 16234 번 인구 이동 정답 코드입니다. 설명은 아래에 있습니다.

N, L, R = map(int, input().split()) #L이상 R 이하 라면 union

board = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    union = [[x, y]]
    queue = [[x, y]]
    while queue:
        x, y = queue.pop(0)
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0 <= nx < N and 0 <= ny < N:
                if not visited[nx][ny]:
                    if L <= abs(board[x][y] - board[nx][ny]) <= R:
                        visited[nx][ny] = True
                        queue.append([nx, ny])
                        union.append([nx, ny])
    return union

ans = 0
while True:
    ''' To debug
    for i in range(N):
        for j in range(N):
            print(board[i][j], end=" ")
        print("")
    print("")'''

    flag = True
    visited = [[False for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                visited[i][j] = True
                union = bfs(i, j)
                num = 0

                for u in union:
                    x, y = u
                    num += board[x][y]
                avg = int(num/len(union))

                for u in union:
                    x, y = u
                    board[x][y] = avg

                if len(union) >= 2:
                    flag = False
    if flag:
        break
    ans += 1

print(ans)

 

문제 접근

각 나라는 상하좌우를 확인하고, 연합이라면 연합의 평균 인구수가 되게끔 인구이동을 합니다.

따라서 모든 노드에 아직 (연합이 만들어지기 전)이라면 bfs를 실행시키고 상하 좌우를 확인하고, 연합을 완성시킵니다.

이를 인구 이동이 멈출 때 까지 반복하고, 반복횟수를 출력합니다.

 

Python 코드 구현

조건에 맞는 연합을 출력하는 함수 bfs를 2차원 행렬의 모든 노드에 실행시킵니다.

방문이 이미 된 경우는 다른 나라와 이미 연합이 된 상태이므로 생략합니다.

while True:
    flag = True
    visited = [[False for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                visited[i][j] = True
                union = bfs(i, j)​

 

연합이 구해졌다면 연합의 평균값을 구해서 연합에 속해있는 모든 나라에 값을 업데이트 합니다.

또한 연합의 길이가 2 이상이라면(연합이 존재한다면)

인구 이동이 진행중이란 뜻 입니다. 따라서 while 문을 종료시키면 안되므로 flag 에 false를 대입합니다.

union = bfs(i, j)
num = 0
for u in union:
    x, y = u
    num += board[x][y]
avg = int(num/len(union))

for u in union:
    x, y = u
    board[x][y] = avg

if len(union) >= 2:
    flag = False

 

마지막으로 모든 노드를 방문하며 연합이 한번도 생기지 않았다면 종료

아니라면, 인구이동에 걸린 날짜를 1증가 시킵니다.

if flag:
    break
ans += 1

 

bfs를 살펴보겠습니다.

 연합과 큐를 선언하고, 큐가 존재할 동안 반복합니다.

해당 나라가 그래프의 범위 안이고, 방문 전 이고,  연합이 되기위한 조건 만족한다면, 연합에 추가합니다.

bfs가 끝나면 연합을 return 합니다.

def bfs(x, y):
    union = [[x, y]]
    queue = [[x, y]]
    while queue:
        x, y = queue.pop(0)
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0 <= nx < N and 0 <= ny < N:
                if not visited[nx][ny]:
                    if L <= abs(board[x][y] - board[nx][ny]) <= R:
                        visited[nx][ny] = True
                        queue.append([nx, ny])
                        union.append([nx, ny])
    return union

 

파이썬 백준 16234 번 인구 이동 최종 코드입니다. 

N, L, R = map(int, input().split()) #L이상 R 이하 라면 union

board = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    union = [[x, y]]
    queue = [[x, y]]
    while queue:
        x, y = queue.pop(0)
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0 <= nx < N and 0 <= ny < N:
                if not visited[nx][ny]:
                    if L <= abs(board[x][y] - board[nx][ny]) <= R:
                        visited[nx][ny] = True
                        queue.append([nx, ny])
                        union.append([nx, ny])
    return union

ans = 0
while True:
    flag = True
    visited = [[False for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                visited[i][j] = True
                union = bfs(i, j)
                num = 0
                for u in union:
                    x, y = u
                    num += board[x][y]
                avg = int(num/len(union))

                for u in union:
                    x, y = u
                    board[x][y] = avg

                if len(union) >= 2:
                    flag = False
    if flag:
        break
    ans += 1

print(ans)

 

백준 16234 번 인구 이동 자세한 설명 및 Python 코드였습니다.

감사합니다.