백준/ Gold 5 문제 , 백준 파이썬 16234 , 인구 이동 [BFS]

백준/ Gold 5 문제 , 백준 파이썬 16234 , 인구 이동 [BFS]

 

 

풀이 시간

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
pypy3 로 통과.
방문 체크 안하고 호출 불러버리면 일수 체크하는데 문제가 생겼다.
한번 바뀐 구역은 다음날이 되어야만 다시 바꿀 수 있다는게 핵심.

 

 

 

문제 출처

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

16234번: 인구 이동

 

 

풀이

 

1. 기본 세팅

 

1. 상하좌우 움직임.

 

2. N,L,R 입력 받기

 

3. N 행의 MAP 리스트 입력

 

 

2. BFS

우선 바꿔줘야하는 구역들을 store에 저장해두고 SUM 변수에 합을 저장해뒀다.

 

이후 store 리스트 길이만큼 나눠준 뒤 각 자리에 배분해주었다.

 

만약 sotre 길이가 1이라면 인구 이동이 없는 지역으로 False 를 리턴한다.

 

이때, 중요한것은 인구 이동이 발생한 구역들의 visited를 True로 다 바꿔줘야한다.

 

아래에서 더 설명하겠다.

 

 

3. BFS 호출 및 처리

 

일 수를 카운트해 줄 cnt 변수를 선언하고 while 문을 돌린다.

 

이때 visited를 while 문 내에 선언하여 while 문이 돌때마다 visited가 초기화 될 수 있도록 해준다.

 

이렇게 하는 이유는 앞쪽에서 인구이동이 일어난 구역을 뒤에서 같은날에 바꿔버리는 것을 방지하기 위함이다.

 

만약 이렇게 안할 경우 최악의 경우 여러번 인구이동이 발생하였음에도 한번의 while 문으로 다 정리가 되어 cnt가 0으로 출력되버리는 현상이 발생 한다.

 

이를 방지하자.

 

return 되는 bfs 값은 result 리스트에 저장해주고 만약 result 리스트에 True가 한개이상 없을 시 이제 더이상 인구 이동이 발생하지 않는 상황이므로 break를 걸어 종료시킨다.

 

 

 

정답

 

 

from collections import deque
import sys
input=sys.stdin.readline

vertical=[1,-1,0,0]
parallel=[0,0,1,-1]

N,L,R=map(int,input().split())
MAP=[list(map(int,input().split())) for _ in range(N)]

def bfs(x,y):
    SUM=0
    store=[]
    dq=deque()
    visited[x][y]=True
    dq.append([x,y])
    store.append([x,y])
    SUM+=MAP[x][y]
    while dq:
        X,Y=dq.popleft()
        for i in range(4):
            mx,my=X+vertical[i],Y+parallel[i]
            if 0<=mx<N and 0<=my<N:
                if visited[mx][my]==False:
                    tmp=abs(MAP[X][Y]-MAP[mx][my])
                    if tmp>=L and tmp<=R:
                        SUM+=MAP[mx][my]
                        dq.append([mx,my])
                        store.append([mx,my])
                        visited[mx][my]=True
    if len(store)!=1:
        a=SUM//len(store)
        for i in range(len(store)):
            MAP[store[i][0]][store[i][1]]=a
        return True
    else:
        return False
    
cnt=0
while True:
    visited=[[False for _ in range(N)] for _ in range(N)]
    result=[]
    for i in range(N):
        for j in range(N):
            if visited[i][j]==False:
                result.append(bfs(i,j))
    if True not in result:
        break
    cnt+=1

print(cnt)