🥇[백준] 16234 인구 이동 (골드5) / 구현, 시간초과 해결

문제요약

나의 코드 및 설명 01 : 77~80%에서 시간초과.. 

• bfs(sx,sy) : 연합 가능한 좌표 탐색하는 bfs 함수이고, 아래의 값들을 구할 수 있다.
  (sx,sy) 부터 상하좌우로 좌표를 이동하면서 방문한다. 현재의 좌표와 다음 좌표의 나라의 인구 차이가 조건에 부합한다면 방문 처리한다.
  temp_total : 방문한 좌표의 인구수를 저장하는 변수
  temp_cnt : 방문한 좌표의 수를 카운트한다.(하나의 연합을 이루는 나라들의 수가 된다.)
  check : 연합이 한 번이라도 생성이 되면 check 변수 값을 +1해준다. 
• bfs() 함수의 작성이 끝났다면, 더 이상 연합이 불가능해질 때까지 while문을 통해 반복을 수행한다.
• 이중 for문을 통해 그리드(board)의 좌표 값(나라)들을 방문하면서, 아직 방문체크되지 않은 나라라면 cnt 변수에 연합번호를 체크하고 bfs()를 돌린다. 이 때, bfs() 함수 내에서 방문 테이블 v의 좌표값을 cnt로 갱신시키는데, 이를 통해 어떠한 나라들이 서로 연합되었는지 확인이 가능하다.
• 딕셔너리에 bfs()를 수행하여 나온 연합번호(cnt : 키), 총 인구수(temp_total//temp_cnt : 값)을 저장한다.
• 다시 이중 for문을 돌면서 방문 테이블(v)에 저장된 값을 딕셔너리(d)의 키로하여, 값을 찾아 board 좌표 값을 갱신한다.
  이 과정에서 불필요한 좌표의 방문이 많아져 시간초과가 발생했다.

from collections import deque

#bfs로 연합 가능한 좌표 방문하여 탐색
def bfs(sx,sy):
    global cnt,l,r,temp_total,temp_cnt,check
    queue = deque()
    queue.append((sx,sy))
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=n:
                continue
            else:
                #현재 좌표의 나라와 다음 좌표의 나라의 인구 차이가 조건에 부합하고,
                if l <= abs(board[ny][nx] - board[y][x]) <= r \
                    and v[ny][nx] == 0: #아직 방문처리 되지 않았다면
                    v[ny][nx] = cnt #방문처리 해준다(cnt로 방문처리하는 이유는 연합하는 나라 구분하기 위해서)
                    queue.append((nx,ny))
                    #나중에 연합을 이루는 각 칸의 인구수를 계산해야 하므로, 방문한 나라의 인구수의 합을 저장한다.
                    temp_total += board[ny][nx]  
                    temp_cnt += 1 #연합을 이루는 나라의 숫자를 카운트한다.
                    check += 1
 

n, l, r = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

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


answer = 0

while True: #연합이 더이상 불가능할 때까지 반복한다
    v = [[0] * n for _ in range(n)]
    cnt = 0
    d = {}
    check = 0
    #나라들을 방문하면서 연합인지 아닌지 체크
    for y in range(n): 
        for x in range(n):
            if v[y][x] == 0: #아직 방문체크 되지않은 나라라면
                cnt += 1 #연합 1, 연합 2, 연합 3,,, 연합한 나라를 구분하기 위한 변수
                v[y][x] = cnt #첫 방문하는 나라의 연합 번호를 방문 테이블에 표시
                temp_total = board[y][x] #첫 방문한 나라의 인구 수를 방문한 나라의 총 인구수 변수에 저장
                temp_cnt = 1 #연합한 나라의 개수 카운트(현재 방문한 나라부터 1부터 카운트)
                bfs(x,y) #bfs돌면서 어떤 나라들이 서로 연합되었는지 확인한다
                d[cnt] = temp_total // temp_cnt #연합 1, 연합 2,,, 연합별로 연합번호에 해당하는 인구수 딕셔너리에 저장

    if len(d) == n*n: #만약 딕셔너리가 입력받은 나라의 개수와 같다면, 연합에 실패한 것이므로
        break #반복문 탈출
    
    ##이 부분에서 시간초과 원인 발생한듯.
    for i in range(1,cnt+1): #연합 번호를 1부터 cnt(마지막으로 저장된 연합번호)까지 돌면서
        #모든 좌표를 탐색
        for y in range(n): 
            for x in range(n):
                #방문테이블에 해당 연합번호가 저장되어있다면
                if v[y][x] == i: 
                    #딕셔너리 d에서 해당 연합번호를 키로 갖는 값으로 갱신
                    board[y][x] = d[i]

    if check == 0: #bfs를 돌았음에도 check가 0이라면 연합할 나라가 없는 것
        break

    answer += 1
                
print(answer)

나의 코드 및 설명 02 : 시간초과 해결

• 주석 단 부분의 소스 코드를 활용하여 시간초과를 해결했다.
  bfs()를 통해 연합한 나라의 좌표를 move_list에 저장하고, 이중 for문으로 방문 테이블에 저장된 연합 번호를 체크하면서 board 좌표값을 갱신한다.
  이를 통해, 예를 들어 연합 번호가 4번까지 있을 때, 방문 테이블의 전체 좌표를 탐색하는 이중 for문을 무려 4번이나 수행했었는데, 한 번만 전체 좌표를 탐색하면 되게 되었고, 시간초과를 해결하여 정답판정을 받을 수 있었다.

while문을 돌면서 방문 테이블(v)에 연합번호가 담기게 된다. 같은 연합번호는 모두 같은 연합이다.

from collections import deque

def bfs(sx,sy):
    global cnt,l,r,temp_total,temp_cnt,check
    queue = deque()
    queue.append((sx,sy))
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=n:
                continue
            else:
                if l <= abs(board[ny][nx] - board[y][x]) <= r and v[ny][nx] == 0:
                    v[ny][nx] = cnt
                    queue.append((nx,ny))
                    temp_list.append((nx,ny)) #연합한 나라의 좌표 저장
                    temp_total += board[ny][nx] 
                    temp_cnt += 1
                    check += 1
 

n, l, r = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

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


answer = 0

while True:
    v = [[0] * n for _ in range(n)]
    cnt = 0
    d = {}
    check = 0
    move_list = []
    for y in range(n):
        for x in range(n):
            if v[y][x] == 0:
                temp_list = []
                cnt += 1
                temp_list.append((x,y)) #연합한 나라의 좌표 저장(현재좌표)
                v[y][x] = cnt
                temp_total = board[y][x]
                temp_cnt = 1
                bfs(x,y)
                move_list.append(temp_list) #bfs 수행 후 move_list에 연합한 나라의 좌표 저장
                d[cnt] = temp_total // temp_cnt


    if len(d) == n*n:
        break

    ##이 부분 고쳐서 시간초과 해결
    time = 0
    for k in move_list: #연합한 나라의 좌표들이 저장된 move_list를 하나씩 꺼내서 살펴본다.
        #k : 각 연합번호에 해당하는 연합한 나라들의 좌표들
        time += 1 #연합 1 부터 시작해서 연합 2, 연합 3,,,
        for i,j in k: 
            if v[j][i] == time:
                board[j][i] = d[time] 

    if check == 0:
        break

    answer += 1
                
print(answer)

피드백

시간 초과를 어떻게 해결해야하나 고민을 많이했던 문제. 고민 끝에 좌표를 직접 리스트에 저장한 후 나중에 하나씩 꺼내어 탐색하는 방식으로 시간 초과를 해결했다. 
문제 풀이 과정에서는 연합 가능한 나라를 찾기 위해 BFS를 활용한 아이디어가 좋았고, 또 연합번호에 따른 인구 수를 저장하기 위해 딕셔너리를 활용한 것도 꽤 만족스러웠다. 다만.. 시간 초과를 해결하는 데에 애먹어서 시간을 꽤나 잡아먹었던 문제.. 많은 문제를 풀어보고 시간을 단축할 수 있도록 숙달해야겠다.