[이코테] DFS/BFS - 인구 이동

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

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

16234번: 인구 이동

사고과정

• 주어진 N by N 정보를 어떻게 그래프 데이터로 만들지?에 대해서 사고가 멈추었다. 인접행렬? 인접리스트? 방식을 생각했으나 도통 답이 안나왔다. 결국 포기하고 답을 보았다. 풀이를 보니 애초에 주어진 N by N 정보를 그래프 데이터로 활용했다. 간선 비용은 따로 기록하지 않고 주어진 그래프 데이터를 참조하면서 비용을 계산했다..
• 해당 문제 풀이를 위한 핵심 단계는 다음과 같다.
  • 1. 주어진 N by N 그래프 데이터, 연합처리용 테이블 용도로 2차원 리스트를 2개 운영했다. 이 때, 연합처리 테이블에서는 연합 ID를 기록해서 어떤 국가(노드)들끼리 연합했는지 알 수 있게 했다.
  • 2. 연합한 국가들 좌표를 담기 위해 리스트 1개를 운영했고 인접한 국가들 BFS 탐색하기 위해 큐 1개를 같이 운영했다.
  • 3. 연햡 ID를 하나씩 증가시키면서 N by N 원소 하나씩 탐색하면서 모든 탐색이 끝나면 인구이동이 끝난 상태를 의미하게 되도록 설정했다. 
• 진짜 very hard하다..많이 연습해야겠다.. 삼성 문제였는데 역시가역시로 삼성은 아무나 가는 곳이 아닌듯..하다 ^^

풀이(스스로 못 푼 풀이)

from collections import deque

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

# 인접한 국가 찾을 방향
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def process(x, y, union_id):
    # 연합 국가 좌표 담을 리스트와 큐 정의
    united_x_y = []
    united_q = deque([])
    # 현재 x,y 좌표 append
    united_x_y.append((x, y))
    united_q.append((x, y))
    # 연합 인구 계산할 변수들
    union[x][y] = union_id
    summary = graph[x][y]
    count = 1
    # 큐가 빌 때까지 반복
    while united_q:
        x, y = united_q.popleft()
        # 인접 국가 탐색
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and union[nx][ny] == -1:
                if L <= abs(graph[x][y]-graph[nx][ny]) <= R:
                    union[nx][ny] = union_id
                    united_x_y.append((nx, ny))
                    united_q.append((nx, ny))
                    summary += graph[nx][ny]
                    count += 1
    # 연합된 국가들 인구 갱신
    for i, j in united_q:
        graph[i][j] = summary // count


total_count = 0  # 인구 이동 횟수
while True:
    union = [[-1] * N for _ in range(N)]  # 연합처리되었는지 확인할 2d 리스트
    union_id = 0  # 연합 ID
    # 주어진 graph 정보에서 원소 하나씩 연합 처리 시작
    for i in range(N):
        for j in range(N):
            if union[i][j] == -1: # 연합이 되지 않은 국가들만 처리
                process(i, j, union_id)
                union_id += 1

    if union_id == (N*N):
        break
    total_count += 1

print(total_count)