[BOJ] 백준 16234 인구이동 python

 

그래프이론을 좀 더 공부해보다가 이런 문제를 발견해서 바로 덥석 풀어봤는데 생각보다 걸리긴했네요.

 

 

 

 

from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, L, R = map(int, input().split())
graph = []
for _ in range (0,N):
    a = list(map(int,input().split()))
    graph.append(a)

#L이상 R이하인 경우에는 모두 열림
dx,dy = [0,0,1,-1],[1,-1,0,0]
def bfs(mapp,cnt):
    visited = [[False for _ in range(0, N)] for _ in range(0, N)]
    pt = []
    for i in range (0,N):
        for j in range (0,N):
            for k in range (0,4):
                ii = i+dx[k]
                jj = j+dy[k]
                if 0 <= ii < N and 0 <= jj < N and L <= abs(mapp[ii][jj] - mapp[i][j]) <= R:
                    pt.append([i,j])
    if len(pt) == 0:
        return cnt
    ptt = []
    for x in pt:
        if visited[x[0]][x[1]] == False:
            deq = deque()
            deq.append(x)
            cnting = 0
            summary = 0
            pts = []
            while deq:
                z = deq.popleft()
                xx,yy = z[0], z[1]
                if visited[xx][yy] == False:
                    pts.append([xx,yy])
                    summary += mapp[xx][yy]
                    cnting += 1
                    visited[xx][yy] = True
                    for i in range (0,4):
                        a,b = xx + dx[i], yy + dy[i]
                        if 0 <= a < N and 0 <= b < N and L <= abs(mapp[a][b] - mapp[xx][yy]) <= R and visited[a][b] == False:
                            deq.append([a,b])
            ptt.append([pts, summary, cnting])
    for y in ptt:
        pts = y[0]
        t = int(y[-2] / y[-1])
        for pt in pts:
            aa,bb = pt[0],pt[1]
            mapp[aa][bb] = t
    return bfs(mapp, cnt + 1)

t = bfs(graph, 0)
print(t)

 

5월로 계약직으로 일하는곳도 종료되는만큼, 프로그래밍에도 좀 더 신경을 써보고자 한다.