인구이동 [BOJ 16234]

1) 문제 접근 방법

 

2-1) 맞은 소스 코드

from collections import deque 

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

board = []
// line은 불필요하다 
line = [[[[False for _ in range(N)] for _ in range(N)] for _ in range(N)] for _ in range(N)]
visited = [[0]*N for _ in range(N)]

sum = 0
cnt = 0 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

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

def dfs(x, y, order):
    
    global cnt
    global sum 
    
    if visited[x][y] == 0:
        cnt += 1 
        sum += board[x][y]
        visited[x][y] = order
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0<=nx and nx < N and 0<=ny and ny < N and line[x][y][nx][ny] == True:
            line[x][y][nx][ny] = False
            dfs(nx, ny, order)
            
// bfs를 선택했다
// bfs의 시간 복잡도는 O(N2)이다.
// 이 때, N이 최대 50임을 고려할 때, 2500이라고 할 수 있다. 
def bfs(x, y, order):
    
    global cnt
    global sum 
    
    q = deque()
    q.append((x,y))
    // visited배열에 order를 기록한다 
    visited[x][y] = order
    sum += board[x][y]
    cnt += 1 
    
    while q:
        x, y = q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            // L이상 R이하에 대한 체크를 여기서 해줘야 한다
            // 여기서 해줌으로써, 별도의 메소드를 만들지 않아도 된다. 
            if 0<=nx and nx < N and 0<=ny and ny < N and visited[nx][ny] == 0 and L<=abs(board[x][y]-board[nx][ny]) and abs(board[x][y]-board[nx][ny]) <=R :
                visited[nx][ny] = order 
                sum += board[nx][ny]
                cnt += 1 
                q.append((nx,ny))
    
     
        
        
day = 0

// 인구 이동은 최대 2000번보다 작거나 같은 입력만 주어진다. 
// 그렇다면 왜 시간 초과가 나지 않는가?
// 6250000*2000 = 12억 5천 아닌가?
while True:
    
    // visited 배열을 선언한다
    // visited 배열에는 같은 연합에는 같은 수를 저장한다 
    visited = [[0]*N for _ in range(N)]
  
    // order는 연합을 구분하기 위해서 사용되는 변수이다. 
    order = 1 
    
    // 연합의 인구를 저장하기 위한 배열을 선언한다. 
    populations = [0]*10000

    // 2차원 board를 탐색한다 
    // 탐색할 때, visited 배열을 통해서 order라는 변수를 기록해 놓는다
    // 즉, 같은 order라는 변수를 가진 위치들은 같은 연합으로 구분한다 
    // 시간복잡도는 이중 for문만의 시간 복잡도는 O(N2)이다
    // 이 때, N이 50이므로, 2500회 돈다고 볼 수 있다. 
    // 그리고 bfs의 시간 복잡도도 마찬가지로 O(N2)이다.
    // 따라서, 전체 시간 복잡도는 O(N4)이다. 
    // 즉, N이 최대 50이므로, 50의 4승 = 6250000이다. 
    for i in range(N):
        for j in range(N):
            if visited[i][j] == 0:
                sum = 0
                cnt = 0 
                // bfs를 통해서 탐색한다 
                bfs(i, j, order)
                // 
                avg = sum // cnt
                populations[order] = avg
                order += 1 
    
    // order가 (N*N)+1이라는 것은, 
    // 즉, board의 모든 점들이 다 다르고, 연합이 없다는 의미이다. 
    if order == (N*N)+1:
        break
    
    // visited를 순회하면서, populations에 저장된 인구값을 
    // board에 업데이트 한다.
    for i in range(N):
        for j in range(N):
            num = visited[i][j]
            board[i][j] = populations[num]

    
    
    day += 1 


print(day)

 

 

2-2) 틀린 소스 코드

import sys
sys.setrecursionlimit(10 ** 6)

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

board = []
line = [[[[False for _ in range(N)] for _ in range(N)] for _ in range(N)] for _ in range(N)]
visited = [[0]*N for _ in range(N)]

sum = 0
cnt = 0 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

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

def dfs(x, y, order):
    
    global cnt
    global sum 
    
    if visited[x][y] == 0:
        cnt += 1 
        sum += board[x][y]
        visited[x][y] = order
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0<=nx and nx < N and 0<=ny and ny < N and line[x][y][nx][ny] == True:
            line[x][y][nx][ny] = False
            dfs(nx, ny, order)
     
        
        
day = 0

while True:
    
    line = [[[[False for _ in range(N)] for _ in range(N)] for _ in range(N)] for _ in range(N)]
    visited = [[0]*N for _ in range(N)]
    lineCnt = 0 

    // line이라는 배열은 불필요하다.
    // dfs or bfs에 그냥 넣어서 하는 것이 가능하다 
    // 이것의 시간 복잡도는 무엇인가?
    // O(N2)에 4를 곱하니 
    // 회당 1만번씩 추가로 돌게 된다 
    // 즉, 2000을 고려하면, 2000만이 추가되는 것이다. 
    for x in range(N):
        for y in range(N):
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
                
                if 0<=nx and nx<N and 0<=ny and ny<N:
                    gap = abs(board[x][y]-board[nx][ny])
                    if L<=gap and gap<=R:
                        line[x][y][nx][ny] = True 
                        lineCnt += 1 
    
    if lineCnt == 0:
        break 
    

    order = 1 
    populations = [0]*10000

    for i in range(N):
        for j in range(N):
            if visited[i][j] == 0:
                sum = 0
                cnt = 0 
                dfs(i, j, order)
                avg = sum // cnt
                populations[order] = avg
                order += 1 
    
    for i in range(N):
        for j in range(N):
            num = visited[i][j]
            board[i][j] = populations[num]

    
    
    day += 1 


print(day)