[이코테] DFS/BFS 구현문제 - 인구 이동 python

난이도 : ●●○ | 풀이 시간 : 40분 | 시간 제한 : 2초 | 메모리 제한 : 512MB | 기출 : 삼성전자 SW 역량테스트

 

문제

• NxN 크기의 땅이 있고, 땅은 1x1개의 칸을 차지한다.
• 각 땅에는 나라가 하나씩 존재한다.
• r행 c열에 있는 나라의 인구수는 A[r][c]이다.
• 인접한 나라 사이에는 국경선이 있다.
• 오늘부터 인구이동이 시작된다.
  • 국경선을 공유하는 나라의 인구 차이가 L이상 R이하라면 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
  • 위 조건에 의해 열어야 하는 국경선이 모두 열리면 인구 이동을 시작한다.
  • 국경선이 열려있어 이동할 수 있으면 그 나라를 오늘 하루 동안 연합이라고 한다.
  • 연합을 이루는 각 나라의 인구수는 (연합의 인구수)/(연합을 이루고 있는 나라의 개수)가 되고, 편의상 소수점은 버린다.
  • 연합을 해체하고 모든 국경선을 닫는다.
• 각 나라의 인구수가 주어질 때 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하라.

 

입력조건

• 첫째 줄에 N, L, R이 주어진다.(1<=N<=50, 1<=L<=R<=100)
• 둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. ()<=A[r][c]<=100)
•  인구 이동 횟수가 2,000번보다 작거나 같은 입력만 주어진다.

출력조건

• 인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

입력예시

2 20 50
50 30
20 40

출력예시

1

 

아이디어

• BFS로 상하좌우로 인접한 나라를 탐색하면서 연합국의 수, 연합의 총 인구수를 증가시킨다.
• 연합에 소속된 모든 나라의 인구수를 (연합의 총인원//연합국의 수)로 갱신한다.

 

코드

from collections import deque
n,l,r = map(int,input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
total_cnt = 0

def bfs(index,x,y):
    q = deque()
    q.append((x,y))
    
    # 연합을 생성함
    unite = []
    # 연합에 현재 국가를 추가함
    unite.append((x,y))
    # 연합번호를 union 리스트에 저장함
    union[x][y]=index
    
    # unite에 소속된 국가의 개수
    cnt = 1
    # unite에 소속된 연합국가의 총 인구수
    summary = graph[x][y]
    
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            
            # 범위 내에 있고 아직 연합에 소속되지 않은 국가라면
            if 0<=nx<n and 0<=ny<n and union[nx][ny]==-1:
            	# 인접한 국가와의 인구수 차이가 l이상 r이하라면
                if l<=abs(graph[x][y]-graph[nx][ny])<=r:
                	# 큐에 추가함
                    q.append((nx,ny))
                    # 연합번호를 기록함
                    union[nx][ny] = index
                    # 총 인구수를 증가시킴
                    summary+=graph[nx][ny]
                    # unite에 소속된 국가의 수를 1 증가시킴
                    cnt += 1
                    # 연합에 추가함
                    unite.append((nx,ny))
                    
    # 연합에 소속된 국가들에 대해서
    for i,j in unite:
    	# 인구수를 업데이트함
        graph[i][j] = summary//cnt

while True:
	# 각 국가들이 소속된 연합번호를 기록할 리스트.
    # 방문여부를 확인하는 데에 사용됨 
    union = [[-1]*n for _ in range(n)]
    
    # 처음 생성되는 연합의 번호는 0
    index = 0
    
    # 아직 아무런 연합에 소속되지 않은 국가라면 그 위치에서부터 bfs를 수행함
    # 한 연합이 생성된 것이니 연합번호인 index를 1 증가시킴
    for i in range(n):
        for j in range(n):
            if union[i][j]==-1:
                bfs(index,i,j)
                index +=1
                
	# 연합이 n*n개가 생성되었다 == 더이상 인구이동이 없다는 뜻이므로 반복 종료
    if index==n*n:
        break
        
    # 인구이동 횟수를 1 증가시킴
    total_cnt +=1
    
print(total_cnt)

 

후기

• 상하좌우로 인접해있는 나라가 연합이 될 수 있다는 걸 한 연합의 크기가 최대 5라는 것으로 잘못 이해했다...
• 더이상 이동이 일어나지 않을 때까지 반복한다는 걸 어떻게 구현해야 하는지 감을 못잡았다. 

 

출처

이것이 취업을 위한 코딩테스트다 with 파이썬