[백준 16234] 인구 이동

1. 문제

www.acmicpc.net/problem/16234

2. 접근 방법

탐색하면 됩니다.

DFS와 BFS 두 가지로 풀어봤는데 차이가 없습니다.

왜죠 ?!!!!

오히려 BFS가 더 느렸습니다

왜죠 ?!!!!

 

저는 이 문제 BFS라고 생각함니다

3. 코드

python

# BFS

from collections import deque

def isBoard(x, y):
    if 0 <= x < N and 0 <= y < N:
        return True
    return False

def BFS(_x, _y):
    global visited, L, R, board, isChange
    q = deque()
    q.append((_x, _y))
    group = deque()
    group.append((_x, _y))

    while q:
        x, y = q.pop()

        for i in range(4):
            tx = x + dx[i]
            ty = y + dy[i]
            if isBoard(tx, ty) and not visited[ty][tx] and L <= abs(board[y][x] - board[ty][tx]) <= R:
                visited[ty][tx] = True
                group.append((tx, ty))
                q.append((tx, ty))

    if len(group) > 1:
        temp_sum = 0
        for i in range(len(group)):
            _x, _y = group[i][0], group[i][1]
            temp_sum += board[_y][_x]
        avg = temp_sum // len(group)
        for _ in range(len(group)):
            _x, _y = group.popleft()
            board[_y][_x] = avg
        isChange = True


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

while True:
    visited = [[False]*N for _ in range(N)]
    isChange = False
    for y in range(N):
        for x in range(N):
            if not visited[y][x]:
                visited[y][x] = True
                BFS(x, y)
    if not isChange:
        break
    else:
        cnt += 1

print(cnt)

# DFS

import sys
sys.setrecursionlimit(2000)

def isBoard(x, y):
    if 0 <= x < N and 0 <= y < N:
        return True
    return False

def DFS(x, y):
    global visited, group_lst, L, R
    visited[y][x] = True
    for i in range(4):
        tx = x + dx[i]
        ty = y + dy[i]
        if isBoard(tx, ty) and not visited[ty][tx] and L <= abs(board[y][x] - board[ty][tx]) <= R:
            group_lst.append((tx, ty))
            DFS(tx, ty)

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

while True:
    visited = [[False]*N for _ in range(N)]
    isChange = False
    for y in range(N):
        for x in range(N):
            group_lst = [(x, y)]
            if not visited[y][x]:
                DFS(x, y)
            if len(group_lst) > 1:
                isChange = True
                temp_sum = 0
                for _x, _y in group_lst:
                    temp_sum += board[_y][_x]
                avg = temp_sum // len(group_lst)
                for _x, _y in group_lst:
                    board[_y][_x] = avg
    if not isChange:
        break
    else:
        cnt += 1

print(cnt)

4. 마치며

참고로 DFS의 경우 재귀 범위를 벗어나기 때문에 임의로 sys.setrecursion(2000)으로 최대 재귀 깊이 한도를 2000으로 늘려줬습니다.

 

그리고 저 두 코드 모두 python3으로 하면 시간 초과 난당 ㅜㅜ 안나게 하려면 연합 만들 때 union쓰면 되는거 같은데, 기억이 나지 않아 정리하고 다시 여기다가 추가 업로드 할 예정