728x90
문제 보기
이 문제는 bfs 문제이다. (+시간 초과 해결)
- 문제 접근
- 인구 차이를 통해서 국경선을 열고 닫으며, 몇 번의 인구 변화가 일어나는지 파악하는 문제이다.
- 국경선을 열 때마다 인구 변화를 일으키는 것이 아니라 전체 국경선 형태를 파악한 후 한 번에 값을 업데이트한다. (시간 초과 관련)
- 국경선을 열 수 없을 때까지 진행한다.
- 알고리즘
- 현재 위치에서 지나갈 수 있는 집합을 파악한다. (원소 위치, 원소 개수, 원소 합) - bfs
- 1번의 과정을 전 구간에 실시한다.
- 값을 업데이트하고 다시 1번으로 돌아간다. 만약 업데이트할 값이 없다면 종료한다.
코드
import sys
from _collections import deque
# 상, 하, 좌, 우
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
def bfs(row, col):
check = False
visited = {(row, col)}
q = deque([(row, col)])
val, cnt = 0, 0
while q:
row, col = q.popleft()
val += arr[row][col]
cnt += 1
for i in range(4):
new_row, new_col = row + dy[i], col + dx[i]
if 0 <= new_row < N and 0 <= new_col < N and (new_row, new_col) not in visited and L <= abs(arr[new_row][new_col] - arr[row][col]) <= R:
q.append((new_row, new_col))
visited.add((new_row, new_col))
check = True
return val // cnt, visited, check
def move():
# 인구 이동
cnt, pre_cnt = 0, 0
while True:
is_Move = False
total_visited = set()
temp = []
for i in range(N):
for j in range(N):
if (i, j) not in total_visited:
value, visited, flag = bfs(i, j)
if flag:
is_Move = True
temp.append((value, visited))
total_visited |= visited
for (value, visit) in temp:
for y, x in visit:
arr[y][x] = value
if not is_Move:
return cnt
cnt += 1
if __name__ == "__main__":
N, L, R = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
print(move())
728x90
'알고리즘 풀이 > 백준' 카테고리의 다른 글
[ 백준 9252 ] LCS 2 - Python (0) | 2020.06.14 |
---|---|
[ 백준 2589 ] 보물섬 - Python (4) | 2020.06.11 |
[ 백준 15683 ] 감시 - Python (0) | 2020.06.10 |
[ 백준 3055 ] 탈출 - Python (0) | 2020.06.09 |
[ 백준 1107 ] 리모컨 - Python (8) | 2020.06.09 |