[백준 16234] 인구이동(파이썬)

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

16234번: 인구 이동

구역을 나누는 건

BFS류의 문제로 많이 풀어봐서

바로 BFS가 생각이 났습니다.

그 다음에 관건은

어떻게 분배를 해주냐는 거였습니다.

우선 BFS로 구역을 전부 구한 후

구역의 합과 구역의 크기를 구한 다음에

분배를 시켜줘야하는데

이건 BFS를 마치고 해야하는 작업이었죠.

저같은 경우에는

분배용 큐를 하나 더 만들어서

BFS를 하면서 분배용 큐에

구역의 위치들을 넣었습니다.

그리고 BFS를 마친 다음에

분배할 값을 구하고

분배용 큐에 있는 요소들의 위치에

분배를 해주었습니다.

 

# 백준 16234 인구이동
from collections import deque

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

A = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * N for _ in range(N)]

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]

# BFS로 인구구역 구함
# 구하면서 임시 q에 넣었던 장소들 저장
# 모든 구역 합 구한 후, 임시q에 넣은 위치에 분배
day = 0
while day <= 2000:
    no = 0
    for r in range(N):
        for c in range(N):
            if not visited[r][c]:
                visited[r][c] = True
                tmp_sum = A[r][c]
                tmp_count = 1
                q = deque()
                q.append((r, c))
                # 분배용 q하나 만듬
                q_d = deque()
                q_d.append((r, c))
                # 먼저 BFS해준다
                while q:
                    nr, nc = q.popleft()
                    for i in range(4):
                        go_r = nr + dr[i]
                        go_c = nc + dc[i]
                        # 범위확인
                        if (go_r < 0 or go_r >= N) or (go_c < 0 or go_c >= N):
                            continue
                        # 방문확인 및 L이상 R이하인지 확인
                        board = A[nr][nc] - A[go_r][go_c]
                        board = abs(board)
                        if not visited[go_r][go_c] and L <= board <= R:
                            visited[go_r][go_c] = True
                            q.append((go_r, go_c))
                            tmp_sum += A[go_r][go_c]
                            tmp_count += 1
                            q_d.append((go_r, go_c))
                # 만약에 구역이 0이라면(인접한 국경에 만족하는 경우가 없다면
                if tmp_count == 1:
                    continue
                # 구역이 있다면 분배가 되므로 인구이동진행했다고 한다.
                no = 1
                # 이제 분배해준다
                q_divide = tmp_sum // tmp_count
                while q_d:
                    d_n, d_r = q_sum.popleft()
                    A[d_n][d_r] = q_divide
    # 다 돌고 인구이동이 없으면 break
    if no == 0:
        break
    # 다음날이 되면 새로운 visited로 상신
    visited = [[False] * N for _ in range(N)]

    day += 1

    # print(A)        
print(day)         

참고로 이 코드는

python으로 제출시

시간초과가 떠서

pypy3로 제출했습니다.

 

이런 류의 문제를 풀 때

처음에는 제대로 분배가 되었는지

확인해보는 것도 중요합니다.

저 같은 경우에는 

처음에 예시에서 주어진

출력값대로 나오긴 했는데

분배가 잘못되었다는 걸 보고

바로 코드를 수정했습니다.

이렇게 케이스를 안따지고 바로 제출하면

'나는 맞게 했는데 왜 틀렸지??'

라면서 해매기 쉽다고 느껴졌습니다

초반에 한 두개 정도라도

제대로 구현이 되었는지 확인하는 습관도

필요하다는 걸 느꼈습니다.

 

++++

어떻게 하면 시간초과가 뜨지 않을지 고민하다가

구글링을 해보니

굳이 모든 구역을 탐색할 필요가 없다는 걸 알게 되었습니다.

서로 교차로

1 3 5 7....

2 4 6 8....

이런 식으로 연합여부를 판단해도 가능합니다.

처음에는 무슨 말인지 몰라서

직접 그림으로 그려봤습니다.

 

ex1)의 케이스를 보겠습니다.

서치한 곳 바로 옆이 연합입니다.

그럼 굳이 옆을 체크할 필요가 없습니다.

 

반대로 ex2)처럼,

연합이 아닌 경우도 있습니다.

연합이 아니라면 역시나 굳이 체크할 필요가 없죠.

그러므로, '격자로 체크해도 된다'

라는 결론을 얻을 수 있습니다.

 

# 백준 16234 인구이동
from collections import deque

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

A = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * N for _ in range(N)]

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]

# BFS로 인구구역 구함
# 구하면서 임시 q에 넣었던 장소들 저장
# 모든 구역 합 구한 후, 임시q에 넣은 위치에 분배
day = 0
while day <= 2000:
    no = 0
    for r in range(N):
        for c in range(r % 2, N, 2):  # 격자로 띌 수 있게 코드를 수정.
            if not visited[r][c]:
                visited[r][c] = True
                tmp_sum = A[r][c]
                tmp_count = 1
                q = deque()
                q.append((r, c))
                q_sum = deque()
                q_sum.append((r, c))
                # 먼저 BFS해준다
                while q:
                    nr, nc = q.popleft()
                    for i in range(4):
                        go_r = nr + dr[i]
                        go_c = nc + dc[i]
                        # 범위확인
                        if (go_r < 0 or go_r >= N) or (go_c < 0 or go_c >= N):
                            continue
                        # 방문확인 및 L이상 R이하인지 확인
                        board = A[nr][nc] - A[go_r][go_c]
                        board = abs(board)
                        if not visited[go_r][go_c] and L <= board <= R:
                            visited[go_r][go_c] = True
                            q.append((go_r, go_c))
                            tmp_sum += A[go_r][go_c]
                            tmp_count += 1
                            q_sum.append((go_r, go_c))
                # 만약에 구역이 0이라면(인접한 국경에 만족하는 경우가 없다면
                if tmp_count == 1:
                    continue
                # 구역이 있다면 분배가 되므로 인구이동진행했다고 한다.
                no = 1
                # 이제 분배해준다
                q_divide = tmp_sum // tmp_count
                while q_sum:
                    d_n, d_r = q_sum.popleft()
                    A[d_n][d_r] = q_divide
    # 다 돌고 인구이동이 없으면 break
    if no == 0:
        break
    # 다음날이 되면 새로운 visited로 상신
    visited = [[False] * N for _ in range(N)]

    day += 1
print(day)   

 

위의 코드를 python3에 통과하기 위해

수정을 가한 부분입니다.

 

어라...똑같은데...

라고 생각하실 수 있겠지만

 

  for r in range(N):
    for c in range(r%2,N,2):#격자로 띌 수 있게 코드를 수정.

이 서치를 해주는 for문에 변경이 있었습니다.

r%2를 해주면서

홀수 행에서는 0을 먼저 서치

짝수 행에서는 1를 먼저 서치

그리고 2씩 증가하면서

각각 짝수,홀수번째만을 서치할 수 있도록

코드를 수정했습니다.

이렇게 수정하니, 파이썬으로도 통과가 되었습니다.

 

처음에 접근할 때에는

'어처피 통과인데 굳이 최적화를 시켜야하나?'

라는 생각도 들었지만

점점 어려운 문제를 접하다보니

최적화 때문에 정답여부가 결정이 된다는 걸 느껴

이 부분은 추가로 학습했습니다.