boj.kr/16234 인구 이동 (gold5) 파이썬 풀이

#풀이1

인구 이동 플래그를 사용하지 않고 풀이하여 일부 케이스에서만 통과했다. 정답 풀이 참고해 인구 이동 플래그 사용하는 풀이로 제출한 결과 성공했다.

 

from collections import deque

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

dy = (0, 0, 1, -1)
dx = (1, -1, 0, 0)

def bfs(y, x):
    dq = deque()
    dq.append((y, x))
    unite_country_set = set()

    while dq:
        (y, x) = dq.popleft()
        unite_country_set.add((y, x))
        chk[y][x] += 1

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0<=ny<N and 0<=nx<N and chk[ny][nx] == 0:
                if L <= abs(board[y][x]-board[ny][nx]) <= R:
                    unite_country_set.add((ny, nx))
                    chk[ny][nx] = chk[y][x] + 1
                    dq.append((ny, nx))

    return list(unite_country_set)

day_count = 0
while True:
    chk = [[0 for _ in range(N+1)] for _ in range(N+1)]
    is_move = 0

    for y in range(N):
        for x in range(N):
            if chk[y][x] == 0:
                chk[y][x] += 1
                unite_country_list = bfs(y, x)

                if len(unite_country_list) > 1:
                    is_move = 1
                    avg = sum([board[ny][nx] for (ny, nx) in unite_country_list]) // len(unite_country_list)
                    for (i, j) in unite_country_list:
                        board[i][j] = avg

    if is_move == 0:
        break
    day_count += 1

print(day_count)

 

true, flase 값만 필요한 경우인지 판단하고 계산은 최소화하고 플래그 변수를 사용해야 헷갈리지 않는다.

 

#2 풀이2

1. 연합되는 좌표들이 없을 때까지 아래를 반복

1.1. 모든 그래프 좌표들에 대해 아래를 반복

1.1.1. 방문체크된 좌표가 아니면 방문체크하고 unite_set을 생성하고 해당 좌표를 저장한 후 아래 bfs를 수행

1.1.1.1. dq에 인자로 받은 좌표를 저장하고 상하좌우 좌표에 대해 방문되지 않았고 연합조건에 맞으면 unite_set, dq에 저장하고 방문체크

1.2. 모든 그래프 좌표를 탐색한 결과 연합된 좌표 개수가 0개이면 반복을 탈출

1.3. 연합된 좌표 개수가 0개가 아니면 cnt를 1 증감

2. cnt를 출력

 

N, L, R = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
dy = (0, 0, 1, -1)
dx = (1, -1, 0, 0)

from collections import deque

def bfs(y, x):
    dq = deque()
    dq.append((y, x))
    while dq:
        (cy, cx) = dq.popleft()
        for i in range(4):
            ny = cy + dy[i]
            nx = cx + dx[i]
            if 0<=ny<N and 0<=nx<N and visited[ny][nx] == 0:
                if L <= abs(graph[cy][cx]-graph[ny][nx]) <= R:
                    unite_set.add((ny, nx))
                    dq.append((ny, nx))
                    visited[ny][nx] += 1

import math
def unite(unite_set):
    tot = 0
    for (y, x) in unite_set:
        tot += graph[y][x]
    for (y, x) in unite_set:
        graph[y][x] = math.trunc(tot/len(unite_set))
    return len(unite_set)-1

cnt = 0
while True:
    unite_cnt = 0
    visited = [[0] * N for _ in range(N)]
    for y in range(N):
        for x in range(N):
            if visited[y][x] == 0:
                visited[y][x] += 1
                unite_set = set()
                unite_set.add((y, x))
                bfs(y, x)
                unite_cnt += unite(unite_set)
    if unite_cnt == 0:
        break
    cnt += 1
print(cnt)

set자료형을 사용해 중복을 방지할 수 있다.

연합국 탐색메서드와 연합연산 메서드를 구분해 작성해야 헷갈리지 않는다.