https://www.acmicpc.net/problem/16234
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 bfs를 이용하여 해결하는 문제였습니다. 배열을 조회하다가 방문하지 않은 곳이 있다면 그 좌표에 한해서 절댓값의 차이가 L 이상 R이하인 곳을 탐색을 한 뒤 각각의 칸들의 평균값을 다시 대입을 해주면 되는 문제였습니다. 단지 까다로웠던 점은 while True: 를 통해 무한 반복할 때마다 visited를 계속 만들어서 계속 반복되게 해야 한다는 점이였습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
from collections import deque
import sys
input = sys.stdin.readline
N, L, R = map(int, input().split())
graph = []
for i in range(N):
graph.append(list(map(int, input().split())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(xPos, yPos):
q = deque()
q.append((xPos, yPos))
visited[xPos][yPos] = 1
count = 1
sum = graph[xPos][yPos]
arr = [(xPos, yPos)]
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 그래프의 범위를 벗어나지 않은경우
if 0 <= nx < N and 0 <= ny < N:
# 방문한 곳이 아니고 차의 절댓값이 L, R 사이일때
if visited[nx][ny] == 0 and L <= abs(graph[nx][ny]-graph[x][y]) <= R:
visited[nx][ny] = 1
sum += graph[nx][ny]
count += 1
q.append((nx, ny))
arr.append((nx, ny))
if count > 1: # count가 2 이상인 경우
ans = sum // count
for a, b in arr: # 해당 지역에 인구 이동
graph[a][b] = ans
return True
return False
count = 0
while True:
visited = [[0]*N for _ in range(N)] # N행 N열짜리 visited리스트
flag = False # 인구 이동할 칸의 유무를 체크하는 플레그 False로 초기화
for i in range(N):
for j in range(N):
if visited[i][j] == 0 and bfs(i, j) == True: # 방문하지 않았고 bfs의 반환값이 참이라면
flag = True
if flag == False: # 인구이동할 칸이 없는 경우
break
elif flag == True: # 인구이동한 칸이 있는 경우 count를 하나 증가
count += 1
print(count)
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 18310: 안테나(Python) (2) | 2020.12.10 |
|---|---|
| 백준 알고리즘 16234: 국영수(Python) (0) | 2020.12.09 |
| 백준 알고리즘 18428: 감시 피하기(Python) (0) | 2020.12.05 |
| 백준 알고리즘 14888: 연산자 끼워 넣기(Python) (0) | 2020.12.05 |
| 백준 알고리즘 18405: 경쟁적 전염(Python) (0) | 2020.12.05 |