백준 16234 인구 이동(Python)

제가 또 간만에 극악의 실행 시간과 극악에 효율성을 가진 알고리즘을 만들어 냈지 뭡니까
느낀 점 : 알고리즘은 매일 안하면 퇴보한다ㅎㅎㅎ

 

질문은 여기

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

16234번: 인구 이동

 

간단한 dfs + 사방탐색인데 ㅇ여러번 돌려줘야 해서 시간이 많이 나온다ㅠㅠㅠ 

포인트는 stack이랑 queue를 따로 만들어줘야 했던 것 

마지막에 인구이동을 시행해야 하기 때문이다!

 

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


def dfs(x,y):
    global visited
    global flag
    stack = []
    queue = [(x,y)]
    population = countries[x][y]
    for dl in delta:
        nx = x + dl[0]
        ny = y + dl[1]
        if -1<nx<N and -1<ny<N and visited[nx][ny] == False and L <= abs(countries[x][y] - countries[nx][ny]) <=R:
            population += countries[nx][ny]
            stack.append((nx,ny))
            queue.append((nx,ny))
            flag = True
    if flag:
        while stack:
            a, b = stack.pop()
            for dl in delta:
                na = a + dl[0]
                nb = b + dl[1]
                if -1<na<N and -1<nb<N and visited[na][nb] == False and (na,nb) not in queue and L<= abs(countries[a][b] - countries[na][nb])<=R:
                    population += countries[na][nb]
                    stack.append((na, nb))
                    queue.append((na,nb))
        new = population // len(queue)
        for q in queue:
            visited[q[0]][q[1]] = True
            countries[q[0]][q[1]] = new
        return
    else:
        visited[x][y] = True
        return

N, L, R = map(int, input().split())
countries = [list(map(int, input().split())) for _ in range(N)]
move = 0
while True:
    flag = False
    visited = [[False for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if visited[i][j] == False:
                dfs(i,j)
    if flag:
        move +=1
        continue
    else:
        break

print(move)