Python 16234번 인구 이동

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

16234번: 인구 이동

 

 

문제는 방식은 간단했다. 처음부터 끝까지 모든 인덱스를 방문해서(이미 방문한 곳은 패스) bfs방식으로 연결된 구간은(인구 이동이 일어나는 구간) result에 set으로 저장을 해서 res에 저장했다.

그리고 res에 저장된 연결된 구간들의 인구의 값을 모두 더하고 나눈 다음 그 구간에 값들을 다시 재분배해줬다.

이와 같은 방식으로 res에 아무것도 저장이 되지 않을때까지(이어진 구간이 없음) 반복해서 며칠이 걸리는지 구했다.

 

---

처음에 계속 시간 초과 오류가 떠서 코드를 여러번 바꿔서 제출했지만 80% 구간에서 python3로는 계속 시간 초과 에러가 떴다ㅠㅠ

일단 시간을 계속 줄이기 위해 visited를 인덱스로 접근할 수 있게 바꿨고 bfs함수 내에서 result가 중복되는게 저장되는걸 방지하기 위해 set를 사용했고 q에 넣을 인덱스값도 미리 방문해서 다른 곳에서 또 방문하지 않도록 했다.

인구의 이동이 일어난 다음에 이동이 일어나지 않을 구간(이미 인구 이동이 일어나서 값이 모두 같아졌고 더이상 일어나지 않는 구간)은 bfs를 돌지 않도록 하면 훨씬 시간이 절약될텐데 어떤 방식으로 그것을 구현할지 마땅히 생각나진 않아서 구현을 못했는데 혹시라도 구현한분 있으면 링크 주시면 감사하겠습니다!!🥺

import sys
from collections import deque
input=sys.stdin.readline
n,l,r = map(int,input().split())
ary =[list(map(int,input().split())) for _ in range(n)]
dx=[1,0,-1,0]
dy=[0,1,0,-1]
'''
먼저 사이클을 찾고 방문한 노드는 방문에 저장

'''
def print_ary(ary,n,cnt):
    for i in range(n):
        print(ary[i])
    print(cnt)
def bfs(startx,starty,visited):
    result={(startx,starty)}
    q=deque([[startx,starty]])
    while True:
        if not q:
            break
        X,Y = q.popleft()
        visited[X][Y]=1
        for idx in range(4):
            x=dx[idx]+X
            y=dy[idx]+Y
            if 0<=x<n and 0<=y<n and not visited[x][y]:
                if l<=abs(ary[x][y]-ary[X][Y])<=r:
                    visited[x][y]=1
                    q.append([x, y])
                    result.add((x,y))
    return result

res=[]
cnt=0
while True:
    visited = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(0,n):
        for j in range(0,n):
            if not visited[i][j]:
                temp = bfs(i,j,visited)
                if len(temp)==1:
                    continue
                res.append(temp)
    # print(visited)
    #calc
    if len(res)==0:
        break
    for lists in res:
        sum=0
        for x,y in lists:
            sum+=ary[x][y]
        # print(lists,sum)
        sum=int(sum/len(lists))
        for x,y in lists:
            ary[x][y]=sum
    # print_ary(ary,n,cnt)
    res=[]

    cnt+=1

    # exit()


print(cnt)
# bfs(visited)