[이.취.코] [백준] Chap 13. BFS_DFS - Q21. 인구 이동

  • 0
  • 0
0
0

1. 인구 이동

A. 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 내 답안

a. 1차 시도 (실패)

from collections import deque

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

graph = []
# diff_graph = [[0] * 4 for _ in range(N)]
diff_graph = []

for i in range(N):
    graph.append(list(map(int, input().split())))

ds = ((-1, 0), (0, 1), (1, 0), (0, -1))

q = deque()
# 좌표, 시간
q.append([0, 0])

while True:
    time = 0
    answer = [[0] * N for _ in range(N)]
    while q:
        x, y = q.popleft()

        for d_i in range(len(ds)):
            dx = x + ds[d_i][0]
            dy = y + ds[d_i][1]

            if 0 <= dx < N and 0 <= dy < N:
                value = abs(graph[x][y] - graph[dx][dy])
                if L <= value <= R:
                    q.append([dx, dy])
                    answer[dx][dy] += 1
                else:
                    continue
            else:
                continue
    total_pop = 0
    total_count = 0

    for i in range(N):
        for j in range(N):
            if answer[i][j] > 0:
                total_pop += graph[i][j]
                total_count += 1

    if total_count == 0:
        break

    for i in range(N):
        for j in range(N):
            if answer[i][j] > 0:
                graph[i][j] = (total_pop // total_count)

    time += 1

print(time)

# print(diff_graph)

    # for i in range(N):
    #     for j in range(N):
    #         diff_list = [0] * 4
    #         for d_i in range(len(ds)):
    #             dx = i + ds[d_i][0]
    #             dy = j + ds[d_i][1]
    #
    #             if 0 <= dx < N and 0 <= dy < N:
    #                 value = abs(graph[i][j] - graph[dx][dy])
    #                 diff_list[d_i] = value
    #             else:
    #                 diff_list[d_i] = 0
    #         diff_graph.append(diff_list)

b. 2차 시도 ()
c. 회고

내 풀이

  • 무한루프 안에 bfs를 구현하였다.

반성

  • 이미 방문한 땅(국경선이 열린 땅)에 대한 체크를 어떻게 해야할지 감이 안왔다.
  • 중첩 반복문 안에 다시 중첩 반복문을 만들어서 시간초과도 발생했다.
    • 단순하게 중첩 반복문을 사용하기보다, 가능하다면 앞 부분에서 작성한 코드를 활용하는 방법을 생각해봐야겠다.

C. 문제 해설

이해한 내용을 바탕으로 작성했습니다.

예제 4번과 5번에 대한 풀이는 다음과 같다.

  1. 모든 땅에 방문한다.
    • 연산의 반복을 방지하기 위해 방문한 땅은 체크한다.
  2. 4방향(상하좌우)를 확인하고 조건(두 나라의 인구 차이가 L명 이상, R명 이하)을 만족하면 조건을 만족하지 않을때까지 bfs를 반복한다.
    • 방문한 땅으로 체크한다.
    • 확인한 땅을 bfs q에 집어넣는다.
  3. bfs q가 끝나면(조건을 만족하는 나라끼리 국경선을 다 열었으면) 인구 이동을 시작한다.
  4. 1번으로 돌아가서 모든 땅을 방문할 때까지(방문한 땅이 전부 체크될 때까지)반복한다.

bfs쪽에서 인구이동할 도시를 2중 for문으로 찾으면 시간초과가 발생한다.


for i in range(N):
    for j in range(N):
        if check[i][j] == group_num:
            graph[i][j] = result // go_count

33773569번 소스 코드 (acmicpc.net)

a. 책 답안

python-for-coding-test/7.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

[1] 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

[2] 16234번: 인구 이동 (acmicpc.net). Baekjoon. (accessed Sep 28, 2021)

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.