[Python] BOJ 16234 - 인구 이동

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

16234번: 인구 이동

# 2018 하반기 삼성SW역량테스트 문제이다.

# 삼성기출에서 자주 나오는 시뮬레이션 문제이다 (BFS를 곁들인..)

 

# '인구 이동'하는 것이 최근 삼성기출에 나온 '미세먼지 안녕!'에서 미세먼지가 확산하는 것과

     비슷하다고 느껴져서 빠르게 접근해서 푼 것 같다.

 

* bfs함수: q에서 pop을 해준 좌표를 기준으로 상하좌우를 탐색하며

              (nx, ny)가 좌표 밖을 벗어나지 않고 방문 안 한 위치이고

              (nx, ny)값과 (x, y)의 값 차이가 L과 R 사이이면

              move[len(move)]와 q에 (nx, ny)를 append해주고, 방문처리를 해준다.

 

              q가 비었으면(모든 좌표 탐색완료 후) move[len(move)]를 확인해

              길이가 1이면 인구 이동이 없는 경우이므로 del move[len(move)]해준다.

 

 

* 메인 함수설명 (26라인 ~)

    매일매일 인구이동해야 할 좌표들을 넣을 move 딕셔너리와 visited배열을 초기화해준다.

  

    모든 땅을 일일이 확인하며 방문하지 않은 위치이면 move[len(move)+1]에 (i, j)를 append한 뒤 

     bfs함수를 실행한다.

     ** (move를 dictionary로 선언해 key와 value로 한 이유는 (0, 0), (0, 1)의 경계선이 열리고

              (2, 1), (2, 2)의 경계선이 열려 같은 날에 떨어진 위치에서 인구 이동이 일어날 수 있기 때문에

              인구 이동이 일어나는 구역별로 따로 저장해주기 위해서이다.

     예를 들어 (0, 0), (0, 1)의 경계선이 열리고 (2, 1), (2, 2)의 경계선이 열린다고 하면 move는

               {1: [(0, 0), (0, 1)], 2: [(2, 1), (2, 2)]} 이런식으로 저장이 된다.

               따라서 40번째 줄부터 인구 이동을 할때 for문을 통해

               (0, 0), (0, 1)인구를 이동시키고 (2, 1), (2, 2)인구를 각각 이동시킬 수 있다.)

 

    모든 땅을 확인한 뒤, move에 원소가 없으면 인구 이동이 더 이상 없으므로 day를 출력하고 종료한다.

    원소가 한개라도 존재한다면 인구 이동을 하고 day를 1증가시킨다. (40 ~ 47라인)

 

import sys
from collections import defaultdict, deque
input = sys.stdin.readline
N, L, R = map(int,input().split())
m = [list(map(int,input().split())) for _ in range(N)]
dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]
q = deque()

def bfs(i, j):
    q.append((i, j))
    visited[i][j] = True
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y+ dy[i]
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                if L <= abs(m[nx][ny] - m[x][y]) <= R:
                    move[len(move)].append((nx, ny))
                    q.append((nx, ny))
                    visited[nx][ny] = True
    
    if len(move[len(move)]) == 1:
        del move[len(move)]

day = 0
while True:
    move = defaultdict(list)
    visited = [[False] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                move[len(move) + 1].append((i, j))
                bfs(i, j)

    if not move:
        print(day)
        break
    else:
    	# 인구 이동
        for i in move:
            s = 0
            for x, y in move[i]:
                s += m[x][y]
            s = int(s / len(move[i]))
            for x, y in move[i]:
                m[x][y] = s
        day += 1

(solved.ac 티어: 골드 5)

 

# 풀고나서 뭔가 유형이 삼성기출이랑 비슷한데? 하고 찾아보니 삼성기출이었다.

   기업마다 자주나오는 유형이 이제 좀 보이는 것 같다.