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

🥚문제

---

🥚입력/출력

---

🍳코드

PyPy3로 통과

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

""" 입력 """
N, L, R = map(int, input().split())
country = [list(map(int, input().split())) for _ in range(N)]


def solve():
    ans = 0

    while True:
        """
        (r1, c1), (r2, c2)가 국경선을 공유할 수 있다면
        border[r1][c1] == border[r2][c2], 같은 코드를 가짐
        """
        border = [[0]*N for _ in range(N)]
        code = 1
        for r in range(N):
            for c in range(N):
                if border[r][c] == 0:
                    bfs(r, c, border, code)
                    code += 1

        """ bfs 수행 후 border 출력하는 코드
        print("bfs 이후 border 상태")
        for border_row in border:
            print(border_row)
        """

        """
        union_info
        union_info[code] = [(r1, c1), (r2, c2), ...]
        같은 code를 공유하는 연합국들의 좌표를 저장한다
        """
        union_info = [[] for _ in range(code)]
        for r in range(N):
            for c in range(N):
                if border[r][c] != 0:
                    union_info[border[r][c]].append((r, c))

        """ union_info 출력하는 코드
        print("union_info")
        for union_info_row in union_info:
            print(union_info_row)
        """

        # 인구 이동 시키기
        stop = True
        for i in range(1, code):
            # 한 국가만 있는 연합은 연합이 아니다
            if len(union_info[i]) <= 1:
                continue
            else:
                stop = False  # 연합이 하나라도 존재하면 stop 하지 않는다

                union_count = len(union_info[i])  # 연합을 이루는 칸의 개수
                union_people = 0  # 연합의 인구 수
                for x in union_info[i]:
                    union_people += country[x[0]][x[1]]
                union_people = union_people // union_count  # 인구 수

                # 인구를 이동시킨다
                for x in union_info[i]:
                    country[x[0]][x[1]] = union_people

        if stop:
            return ans  # 더이상 이동 없음. loop 종료, 함수 반환
        else:
            ans += 1  # 날짜 카운트 증가

    return ans


def bfs(r, c, border, code):
    q = deque([(r, c)])
    border[r][c] = code
    moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    while q:
        r, c = q.popleft()
        for move in moves:
            new_r = r + move[0]
            new_c = c + move[1]
            if 0 <= new_r < N and 0 <= new_c < N:
                if border[new_r][new_c] == 0:
                    # 인구 차이
                    diff = abs(country[r][c] - country[new_r][new_c])
                    if L <= diff <= R:
                        # 국경선을 공유
                        border[new_r][new_c] = border[r][c]
                        q.append((new_r, new_c))


print(solve())

---

🧂아이디어

탐색, 구현

• BFS를 이용하여 인접한 나라와 국경을 공유할 수 있는지 판단한다.

• (r1, c1)과 (r2, c2)가 국경을 공유한다면 같은 code를 가진다.

• 이를 border라는 리스트에 나타낸다.

  • 예제 4를 입력했을 때,
  • 루프를 돌 때마다 border의 상태를 출력하면 아래와 같다 border[r1][c1], border[r2][c2]가 같은 값을 가지면 국경을 공유하는 연합국이다.
    • 첫 bfs이후: (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 1)에 위치한 국가들이 국경을 공유한다. 인구 이동.
    • 두번째 bfs이후: (1, 2), (2, 1), (2, 2)에 위치한 국가들이 국경을 공유한다. 인구 이동.
    • 세 번째 bfs이후: 국경을 공유하는 나라가 하나도 없으므로 (한 국가만으로 이루어진 연합은 국경을 공유하는 것으로 보지 않는다) 인구 이동은 발생하지 않는다. 루프 중단.

• (연합의 인구수) / (연합을 이루고 있는 칸의 개수)를 구하거나, 인구 이동 후 인구수를 업데이트 해줄 때 좀 더 빠르고 편리하게 접근하기 위해서 union_info에 같은 연합인 나라들의 좌표를 저장해둔다.

  • 위와 같이, 예제 4를 입력하고 루프를 돌 때마다 union_info의 상태를 출력하면 아래와 같다 여기에서도 마찬가지로, 한 국가만으로 이루어진 연합은 국경을 공유하는 것으로 보지 않는다!

• 국경을 공유하는 나라들이 없다면, 더 이상 이동이 없음을 나타내는 플래그 stop을 이용하여 loop를 빠져나온다.