16234 인구이동 파이썬 (재시도 0)

풀이 참고 출처:https://pacific-ocean.tistory.com/375

[백준] 16234번(python 파이썬)

 

문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

 

 

생각한 입력 및 변수 :

1.N,L,R

2.인구수 배열 A

3. 연합에 속한 여부배열  

 

추가해야 했던 변수들은

인구이동이 일어난 여부 불변수 

연합에 속한 지역 좌표 모음을 가진 배열( 이게 있으면 인구수 및 계산이 가능하다.)

bfs를 위한 need_visit

인구이동 일어난 일 변수

 

내가 생각한 흐름은

 -1 인접한 두정점의 인구수 차이가 L이상R이하인 곳 찾기

 -2 해당 지역의 연합에 속한 여부 1로 변경

 -3 인구이동 계산 

 -4 표시된곳 초기화

인데, 일단 4번도 잘못 생각했고,

두정점의 인구수 차이가 L이상 R이하인 곳을 구하기 위해서 일단 배열범위 내 존재여부랑, 인구수 차이 조건을 

사용하는 함수가 필요한 것 까진 캐치했으나, 인접한 연합을 전부 확인하는 방법을 몰랐다.

 

연관된 요소 종류, 요소의 개수를 구하는 방법이 필요했다.

해결 방법은 그래프 순회인 bfs 였는데, 사실 dfs를 써도 상관없었다.

 

다만 한가지 의문은 연관요소를 어떻게 전부 찾아서 저장하는가였는데,

참고한 코드에서 while문을 통해 인접한 요소들에 대해서도 각각 그요소에 인접한 요소들을 확인하는 방식이었다.

 

결론적으로 구현에 그래프이론이 합쳐진 문제였다.

변수설정도 부족한게 있었고, 흐름 설계도 더 제대로 짜야할 것 같다.

 

 

def 확인 함수( 현재 지역좌표 i,j):

   need_visit(방문해야할 지역큐)와 

   방문한 지역(인접한지역)을 담을 temp를 새성하고

   초기값 작업

   

  while 방문해야할 지역이 없을 때  까지:

   원소를 방문해야할 지역에서 뽑아서

   for i in range(4)

     인접요소 에 대해서 좌표 생성 후( 인접요소확인용 이동 배열을 사용)

     각각에 대해서

      if  배열 범위내에 있고, 연합이 생성된적이 없는ㄴ지

           if 현재 좌표의 인구수가 조건내에 들어가는지 

                만족 시 연합여부(visit) 1로 변경

                 need_visit과 temp에 원소 추가

    temp 반환

 

 

while True:

   연합인 지역인지 여부를 체크할 visit배열 선언

   인구이동이 일어났는지 여부체크할 isUnion 선언

   모든 좌표에 대해서 

   이중 for문  :

     if 연합이 안되어 있는 지역이면 :

            temp에 연합한 지역들을 담는다.

            if temp가 1개 이상이면 ( 연합한 지역이 2개이상이어야 의미가 있다.):

               isUnion을 True로 한다.

               그 후 연합 지역 별 변경된 인구수를 구해서 적용시킨다.

     if  인구이동이 안일어났으면 break

     인구이동이 일어난 날짜 +1

 

 

 

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

#N,L,R 입력받기
N,L,R=map(int,input().split())
#인구수 배열
A=[list(map(int,input().split())) for _ in range(N) ]

cnt=0
dy=[-1,0,1,0]
dx=[0,1,0,-1]

#인접한곳중 조건에 맞는 모든 지역을 temp에 담아 넣는데, 이를 bfs로 이용했다.
def UnionCheck(i,j):
    need_visit=deque() #방문해야할 지역 큐로
    need_visit.append([i,j])
    temp=[]
    temp.append([i,j])#총 연합 지역을 담을 큐이다.
    while need_visit:
        y,x=need_visit.pop()
        for i in range(4):
            ny=y+dy[i]
            nx= x + dx[i]
            if 0<=nx<N and 0<=ny<N and visit[ny][nx]==0: # 범위내에 들어가고, L과 R사이에 범위에 존재하면
                if L<=abs(A[ny][nx]-A[y][x])<=R:
                    visit[ny][nx]=1 # 연합을 맻은 곳은 1로 표시
                    need_visit.append([ny,nx])#큐에 넣어서 bfs 활용
                    temp.append([ny, nx])#방문한 지역 따로 저장
    return temp

while True:
    visit=[[0]*N for _ in range(N)] # 이미 연합인 지역 체크
    isUnion=False
    for i in range(N):
        for j in range(N):
            if visit[i][j] == 0: # 방문을 안한 지역이면 1로 만들고 연합이 이미 돼어있다는 표시.
                visit[i][j]=1
                temp=UnionCheck(i,j)
                if len(temp)>1: # 연합을 한지역이상 했으면
                    isUnion=True
                    num=sum(  [ A[y][x] for y,x in temp ]  )//len(temp) #인구수 분배
                    for y,x in temp:
                        A[y][x]=num
    if not isUnion: #연합이 없다는 얘기는 이동이 없었다는 얘기이므로로
       break
    cnt+=1
print(cnt)