백준 16234 : 인구 이동(파이썬)

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

16234번: 인구 이동

 해당 문제의 핵심은 BFS 이다.

 큐에 좌표 값을 넣고 해당 좌표값을 기준으로 근접한 셀과의 인구 차이가 L 과 R사이에 있다면, 방문 처리를 하고 인구이동할 연합의 영역을 결정해주고 이동시켜주면 된다.

 문제를 계속해서 풀다보니 어느정도 접근법은 이해하기 시작했는데, 아직도 코딩이 익숙하지가 않다. 하다보면 나아지겠지

 

1. 전체 코드

메모리 : 131644 KB 시간 : 1240 ms

n, l, r = map(int, input().split())
# Board
board = [list(map(int, input().split())) for _ in range(n)]
# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y, visited) :
    q = []
    data = []
    q.append([x, y])
    data.append([x, y])
    visited[x][y] = True
    while q :
        x, y = q[0][0], q[0][1]
        del q[0]
        for i in range(4) :
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n : continue
            if abs(board[nx][ny] - board[x][y]) >= l and abs(board[nx][ny] - board[x][y]) <= r and not visited[nx][ny] :
                visited[nx][ny] = True
                q.append([nx, ny])
                data.append([nx, ny])
    total = 0
    for i, j in data :
        total += board[i][j]
    result = int(total / len(data))
    for i, j in data :
        board[i][j] = result
    return len(data), visited

def solve() :
    count = 0
    while True :
        visited = [[False]*n for _ in range(n)]
        able = False
        for i in range(n) :
            for j in range(n) :
                if not visited[i][j] :
                    num_data, visited = bfs(i, j, visited)
                    if num_data > 1 :
                        able = True
        if not able : break
        count += 1
    return count
count = solve()
print(count)