https://www.acmicpc.net/problem/16234
์์ด๋์ด
1. ํ์ด์ฌ ์ด์
- ์ฒ์์ dfs๋ก ์ ๊ทผํ๋๋ฐ Python3๋ก ์ฑ์ ํ๋ฉด 80% ์์ ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ค. (pypy๋ก๋ ํต๊ณผ)
- ํฌ๊ธฐํ๊ณ bfs๋ก ์ ๊ทผํ๋๋ฐ ๋ ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํด์ ์กฐ๊ฑด์ ๋ช ๊ฐ ์ถ๊ฐํ๋ ํต๊ณผ๋จ.
- c++ ์์ผ๋ฉด dfs๋ก ํต๊ณผํ์ ๊ฑฐ ๊ฐ๋ค.
2. ๊ตฌํ ํํธ๋ ํฌ๊ฒ ๋ ๊ฐ๋ก ๋๋ด๋ค.
- ๊ตญ๊ฒฝ์ ์ด๊ธฐ
- ์ธ๊ตฌ์ ๋ถ๋ฐฐ
์ฝ๋ ์ค๋ช
๊ธฐ๋ณธ์ ์ผ๋ก ์ด์ค for๋ฌธ์ ์ฌ์ฉํด์ ๊ฐ ์์น๋ง๋ค bfs๋ฅผ ์คํํ๋ค.
์ฌ๊ธฐ์ ๋ฐฉ๋ฌธํ ์ ์ด ์๊ฑฐ๋ check
ํจ์๋ฅผ ํตํด bfs๋ฅผ ์คํํ ์ง ๋ง์ง ๊ฒฐ์ ํ๋ค.
์ธ๊ตฌ์ด๋์ด ์์ ๋๊น์ง ๊ณ์ ๋ฐ๋ณตํด์ผ ํ๋ฏ๋ก population_flag๋ผ๋
๋ณ์๋ฅผ ์ฌ์ฉํด ์ธ๊ตฌ๋ณํ๋ฅผ ํ์ํ๋ค.
def bfs(x,y):
global population_flag
union_list = []
union_person = 0
deq = deque()
visited[x][y] = True
union_list.append([x,y])
union_person += country[x][y]
deq.append([x,y])
while deq:
a,b = deq.popleft()
for i in range(4):
nx, ny = a + dx[i], b + dy[i]
if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
if L <= abs(country[a][b] - country[nx][ny]) <= R:
visited[nx][ny] = True
deq.append([nx,ny])
union_list.append([nx,ny])
union_person += country[nx][ny]
union_len = len(union_list)
์ฐํฉํ ๋๋ผ๋ฅผ ๋ด์ ๋ฆฌ์คํธ์ ์ฐํฉ ์ธ๊ตฌ์๋ฅผ ์ ์ฅํ ๋ณ์๋ฅผ ์ค์ ํ๋ค.
์, ํ, ์ข, ์ฐ๋ก ์ธ๊ตฌ ์ฐจ์ด ์กฐ๊ฑด์ ํ์ธํ๋ฉฐ bfs ํ์ํ๋ค.
ํ์ ๋ฃ์ ๋๋ง๋ค union_list
์ union_person
์ ์
๋ฐ์ดํธํด์ค๋ค.
def check(x, y):
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if L <= abs(country[x][y] - country[nx][ny]) <= R:
return 1
return 0
์ด ํจ์๋ ์๊ฐ ์ด๊ณผ ๋๋ฌธ์ ์ถ๊ฐ๋ก ๋ง๋ ํจ์๋ค. ์ฐํฉ๊ตญ๊ฐ๊ฐ 1๊ฐ๋ผ๋ฉด bfsํจ์๋ฅผ ํธ์ถํ ํ์๊ฐ ์์ผ๋ฏ๋ก
๋ฏธ๋ฆฌ ์ฃผ์ ๊ตญ๊ฐ์ ์ธ๊ตฌ์ ์ฐจ์ด๋ฅผ ํ๋จํด ๋ฆฌํด์ ํด์ค๋ค.
์ ์ฒด ์ฝ๋
import sys
from collections import deque
N, L, R = map(int,input().split())
country = []
dx = [1,-1,0,0]
dy = [0,0,1,-1]
population_flag = True
result = 0
for _ in range(N):
country.append([int(x) for x in sys.stdin.readline().rstrip().split()])
def bfs(x,y):
global population_flag
union_list = []
union_person = 0
deq = deque()
visited[x][y] = True
union_list.append([x,y])
union_person += country[x][y]
deq.append([x,y])
while deq:
a,b = deq.popleft()
for i in range(4):
nx, ny = a + dx[i], b + dy[i]
if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
if L <= abs(country[a][b] - country[nx][ny]) <= R:
visited[nx][ny] = True
deq.append([nx,ny])
union_list.append([nx,ny])
union_person += country[nx][ny]
union_len = len(union_list)
if union_len >= 2:
for u in union_list:
country[u[0]][u[1]] = union_person // union_len
population_flag = True
def check(x, y):
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if L <= abs(country[x][y] - country[nx][ny]) <= R:
return 1
return 0
while population_flag:
population_flag = False
visited = [[False] * N for _ in range(N)]
for i in range(N):
for j in range(N):
if not visited[i][j] and check(i,j):
bfs(i,j)
if population_flag:
result += 1
print(result)
์๋๋ dfs๋ก ์์ฑํ ์ฝ๋
import sys
sys.setrecursionlimit(10**4)
N, L, R = map(int,input().split())
country = []
dx = [1,-1,0,0]
dy = [0,0,1,-1]
for _ in range(N):
country.append([int(x) for x in sys.stdin.readline().rstrip().split()])
visited = [[False]*N for _ in range(N)]
def dfs(x,y):
global union_person
visited[x][y] = True
union_list.append([x,y])
union_person += country[x][y]
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
if L <= abs(country[x][y] - country[nx][ny]) <= R:
dfs(nx,ny)
population_flag = True
result = 0
while population_flag:
population_flag = False
visited = [[False] * N for _ in range(N)]
for i in range(N):
for j in range(N):
if not visited[i][j]:
union_list = []
union_person = 0
dfs(i,j)
union_len = len(union_list)
if union_len >= 2:
population_flag = True
for u in union_list:
country[u[0]][u[1]] = union_person//union_len
if population_flag:
result += 1
print(result)
'๐งฉ Problem Solving > [๋ฐฑ์ค]' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 18111 ๋ง์ธํฌ๋ํํธ (python ํ์ด์ฌ) (4) | 2022.06.23 |
---|---|
[๋ฐฑ์ค] 1107 ๋ฆฌ๋ชจ์ฝ (python ํ์ด์ฌ) (0) | 2022.06.22 |
[๋ฐฑ์ค] 1389 ์ผ๋น ๋ฒ ์ด์ปจ์ 6๋จ๊ณ ๋ฒ์น (python ํ์ด์ฌ) (0) | 2022.06.19 |
[๋ฐฑ์ค] 7562 ๋์ดํธ์ ์ด๋ (python ํ์ด์ฌ) (0) | 2022.06.18 |
[๋ฐฑ์ค] 11404 ํ๋ก์ด๋ (python ํ์ด์ฌ) (0) | 2022.06.18 |