Easy is Perfect

[백준] 16234번 인구 이동 _ 문제 풀이

  • melonicedlatte
  • Mar 29, 2021


1. 문제

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

2. 풀이

삼성 SW 역량테스트 문제입니다. 풀이 순서는 아래와 같습니다.

BFS를 이용하면 되는 문제입니다. BFS를 사용할 때, is_visited 배열을 생성하여 만들었는데, 이번 경우에는 벽을 기준으로 다른 나라에서 한 나라로 접근할 수 있는 경우의 가지수가 4가지 입니다. 그래서 저는 visited를 3중 배열로 만들어, 4개의 방향에서 각각 방문해도 가능할 수 있게 배열을 생성했습니다.

from collections import deque
N, L, R = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
# 상우하좌
dr = [-1,0,1,0]
dc = [0,1,0,-1]
answer = 0

def get_yeonhap():
    global answer
    yeonhap_list = []
    is_visited = [[[False] * 4 for __ in range(N) ] for _ in range(N)]
    round_queue = deque()
    for r in range(N):
        for c in range(N):
            round_queue.append((r,c))
            this_yeonhap = []
            while len(round_queue):
                this_idx = round_queue.popleft()
                this_yeonhap.append(this_idx)
                for side_i in range(4):
                    next_r = this_idx[0] + dr[side_i]
                    next_c = this_idx[1] + dc[side_i]
                    # out of index
                    if next_c < 0 or next_c >= N or next_r < 0 or next_r >= N or is_visited[next_r][next_c][side_i]:
                        continue
                    is_visited[next_r][next_c][side_i] = True
                    # L과 R 사이에 있으면
                    if L <= abs(A[next_r][next_c]-A[this_idx[0]][this_idx[1]]) and abs(A[next_r][next_c]-A[this_idx[0]][this_idx[1]]) <= R:
                        round_queue.append((next_r, next_c))
            yeonhap_list.append(this_yeonhap)

    is_changed = False
    for yeonhap in yeonhap_list:
        if len(yeonhap) == 1:
            continue
        yeonhap = list(set(yeonhap))
        avg = sum([A[r][c] for r, c in yeonhap])//len(yeonhap)
        for r, c in yeonhap:
            if A[r][c] - avg:
                is_changed = True
            A[r][c] = avg
    if is_changed:
        answer += 1

for _ in range(2000):
    get_yeonhap()
print(answer)



Search