시뮬레이션 2 - 인구 이동 (골드 4)

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

16234번: 인구 이동

 

---

 

문제 접근

개인적으로 시뮬레이션 문제들은 처음 보았을 때 매우 복잡해 보인다 라는 특징이 있었다.

이번 문제에서도 "쉽지 않겠구나"라는 생각에 풀기 전부터 어렵다고 느끼는 부분이 있었다.

 

하지만, 스터디 그룹에서 그래프 탐색을 이용하면 된다.라는 힌트를 얻고 세세하게 잘 푼다면 풀 수 있다는 마음으로 풀었다.

 

결론적으로 그림을 그려 BFS를 탐색하며 어떠한 처리를 해주어야 할 것인가 고민하여 문제접근을 하였고

당장 머릿속에서 떠오르지 않더라도 코드를 작성하며 머리가 정리되는 느낌이 들었다.

 

문제 풀이

처음 시작이 중요하다

먼저 문제의 핵심이 되는 키워드를 정리하였다.

# 키워드 : 그래프 탐색 : bfs
# 인접한 4 방향으로 탐색 후 ->
# 리스트에 l, r 사이를 만족하는 국가를 저장
# 저장 한 모든 국가의 평균 값을 계산 후 모든 국가에 저장

# 모두 찾아도 인구 이동이 없을 시 -> break

 

그리고 "정사각형이니 상하좌우만 국가의 이동이 있을 수 있고, 인접한 경우의 인구수의 차이를 구하여 탐색할 국가들을 하나씩 늘리는 BFS를 구현해야겠다. "라는 생각으로 BFS 함수를 먼저 구현하였다.

 

def bfs(r, c, visited):
    if visited[r][c]:
        return False

    q = deque()
    q.append((r, c))
    visited[r][c] = True
    united = [(r, c)]
    hap = graph[r][c]
    count = 1
    while q:
        cur_r, cur_c = q.popleft()
        for i in range(4):
            next_r, next_c = cur_r + dy[i], cur_c + dx[i]
            # 인덱스 처리와 방문 여부
            if 0 <= next_r < N and 0 <= next_c < N and not visited[next_r][next_c]:
                if graph[cur_r][cur_c] >= graph[next_r][next_c]:
                    dif = graph[cur_r][cur_c] - graph[next_r][next_c]
                else:
                    dif = graph[next_r][next_c] - graph[cur_r][cur_c]
                if L <= dif <= R:
                    count += 1
                    visited[next_r][next_c] = True
                    hap += graph[next_r][next_c]
                    united.append((next_r, next_c))
                    q.append((next_r, next_c))
    if count > 1:
        avg = hap//count
        for i in united:
            graph[i[0]][i[1]] = avg
        return True
    return False

 

지금은 방문처리를 위한 vistied 파라미터가 추가되어 있지만 처음에는 이전 사용한 전형적인 BFS를 구현하여 생각하였다.

 

1. united 리스트에 국경스트를 저장,

2. bfs 순회하며 합을 구해 평균값을 계산

3. for 문을 통해 다시 평균 인구수로 graph의 값을 변경

 

좋다. 중간중간 코드가 잘 동작하는지 break point를 이용하여 잘 작동하는지 확인하였다.

 

bfs 함수를 잘 구현하였으니, 이제 모든 graph를 탐색하며 bfs를 실행하고, 만약 모든 곳에서 인구이동이 이루어지지 않으면 break를 사용하여 while 문을 탈출하면 되겠다.라는 생각이 들었다.

 

그러기 위해서는 visited 방문처리 로직을 조금 수정해야 했다.

 

처음에는 global를 이용하여 처리를 해주려고 했지만 쉽지 않았다.

 

while True:
    visited = [[False] * N for _ in range(N)]

    finish = True

    for i in range(N):
        for j in range(N):
            if bfs(i, j, visited):
                finish = False

    if finish:
        break
    day += 1

print(day)

 

결국 함수의 return 값을 이용하여 한 번도 인구 이동이 이루어지지 않음을 확인하는 로직을 구현하였다.

 

한 번이라도 인구이동이 이루어져서 평균값이 된 나라가 생긴다면,

visited는 True로 바뀌어 if 문을 통해 finish 변수는 False 가 되어 break 문을 실행하지 않게 된다.

 

전체 소스 코드

# 1월 31일 수요일
# 인구 이동 시뮬레이션 2
# 골드 4
# 그래프
from collections import deque

N, L, R = map(int, input().split())

graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

# print(graph)

q = deque()
united = []  # 국경이 합쳐지는 국가들을 저장하기 위한 리스트

dy = [-1, 1, 0, 0]  # 상 하 좌 우
dx = [0, 0, -1, 1]


oneday = []


def bfs(r, c, visited):
    if visited[r][c]:
        return False

    q = deque()
    q.append((r, c))
    visited[r][c] = True
    united = [(r, c)]
    hap = graph[r][c]
    count = 1
    while q:
        cur_r, cur_c = q.popleft()
        for i in range(4):
            next_r, next_c = cur_r + dy[i], cur_c + dx[i]
            # 인덱스 처리와 방문 여부
            if 0 <= next_r < N and 0 <= next_c < N and not visited[next_r][next_c]:
                if graph[cur_r][cur_c] >= graph[next_r][next_c]:
                    dif = graph[cur_r][cur_c] - graph[next_r][next_c]
                else:
                    dif = graph[next_r][next_c] - graph[cur_r][cur_c]
                if L <= dif <= R:
                    count += 1
                    visited[next_r][next_c] = True
                    hap += graph[next_r][next_c]
                    united.append((next_r, next_c))
                    q.append((next_r, next_c))
    if count > 1:
        avg = hap//count
        for i in united:
            graph[i[0]][i[1]] = avg
        return True
    return False


day = 0
while True:
    visited = [[False] * N for _ in range(N)]

    finish = True

    for i in range(N):
        for j in range(N):
            if bfs(i, j, visited):
                finish = False

    if finish:
        break
    day += 1

print(day)


# 키워드 : 그래프 탐색 : bfs
# 인접한 4 방향으로 탐색 후 ->
# 리스트에 l, r 사이를 만족하는 국가를 저장
# 저장 한 모든 국가의 평균 값을 계산 후 모든 국가에 저장

# 모두 찾아도 인구 이동이 없을 시 -> break

 

처음 틀린 원인은 잘못된 구현이었다.

 

global 변수로 break 탈출문을 구현했었던 시행착오였다.

 

 

---

피드백 

 

왜 이문제가 시뮬레이션 문제인가?라는 의문점이 들었다. 문제 해결 후  그래프 탐색 문제라고 생각이 들었다.

 

chat gpt의 답변

 

시뮬레이션의 특징

1. 상세한 과정 추적: 시뮬레이션 문제는 각 단계에서 일어나는 상세한 변화를 모두 추적하며, 각 단계에서의 상태 변화가 중요합니다.
2. 다양한 알고리즘과 자료구조의 혼합 사용: 시뮬레이션 문제는 특정 알고리즘에 국한되지 않고, 필요에 따라 다양한 알고리즘과 자료구조를 혼합하여 사용합니다.
3. 조건 분기와 예외 처리: 실제 상황을 모델링하는 경우가 많기 때문에, 다양한 조건 분기와 예외 상황을 처리하는 로직이 필요합니다

인구 이동 문제에서 BFS와 그래프 탐색 알고리즘이 사용되긴 하지만, 단순한 그래프 탐색 문제를 넘어서는 복잡도를 가지고 있습니다. 이 문제는 다음과 같은 이유로 시뮬레이션 문제로 분류됩니다:

1. 단계별 처리: 각 단계에서 인구 이동 조건을 확인하고, 연합을 형성한 후 인구를 이동시키는 과정이 반복적으로 수행됩니다. 이 과정에서 매 단계의 상태를 정확히 추적해야 합니다.
2. 조건적 상호 작용: 인접한 나라들 사이의 인구수 차이를 확인하고, 특정 조건(L명 이상, R명 이하)을 만족할 때만 인구 이동이 발생합니다. 이는 각 단계에서 다양한 조건을 확인하고, 해당 조건에 따라 다른 행동을 취해야 한다는 점에서 시뮬레이션의 특징을 보여줍니다.
3. 복잡한 상태 관리: 연합이 형성되고 해체되며, 연합 내의 인구 이동 후 각 나라의 인구수가 갱신되는 과정은 복잡한 상태 관리를 요구합니다. 이는 시뮬레이션 문제에서 자주 보이는 특징입니다.

따라서, 이 문제는 단순한 그래프 탐색보다는 여러 단계의 처리와 복잡한 상태 관리가 필요한 시뮬레이션 문제로 분류됩니다.