๐ ๋ฐฑ์ค 7576 - ํ ๋งํ
๐ก ๋์ ํ์ด
๋์ ์์ค์์๋ ์ด๋ ค์ ๋ค... ์ต์ ํ ๋งํ ๊ฐ 1๊ฐ์ผ ๊ฒฝ์ฐ์๋ ์ ๊ตฌํ ์ ์์๋๋ฐ, 2๊ฐ ์ด์์ธ ๊ฒฝ์ฐ๋ ๋์ ํ ์๊ฐ์ด ๋์ง ์์๋ค.
๊ทธ๋์ ๋ค๋ฅธ์ฌ๋์ ์ฝ๋๋ฅผ ์กฐ๊ธ ์ฐธ๊ณ ํ๋๋ฐ BFS
๋ฅผ ๋์์ 2๊ฐ๋ฅผ ๋๋ฆฌ๋ ๋ฐฉ๋ฒ์ ์์ ์๊ฐ๋ ๋ชปํ๊ณ ๊ทธ๋ฌ๋ค ๋ณด๋๊น ํจ์์ ์ฝ๋๋ ์ด์ ์ ํ๋ ๋ฐฉ๋ฒ๊ณผ๋ ์กฐ๊ธ ๋ฌ๋ผ์ ๊ณ ๋ฏผํ๋ฉฐ ๋ฌธ์ ๋ฅผ ํธ๋๋ผ ๋ฐ๋์ ์ ์์๋ฒ๋ ธ๋ค.
์ฒ์์ ์ต์ ํ ๋งํ ๊ฐ 2๊ฐ ์ด์ ์์ ๋ ์ผ์ด์ค๋ฅผ ํ๋์ฉ ๋ํด์ ๋ ๊ฐ๋ฅผ ๋ํด์ฃผ๋ฉด ๋ ์ค ์์๋ค. ์ปดํจํ ์ ์ผ๋ก ์๊ฐํ์ง ์๊ณ ๋ดํค๋ ๋๋ก ์๊ฐํด๋ฒ๋ ค์ ์ ๋๋ ๋ฐฉ๋ฒ์ผ๋ก ๊ตฌํํ๋ ค๋๊น ๋จธ๋ฆฌ๊ฐ ๊ผฌ์ฌ๋ฒ๋ ธ๋ค.
๊ทธ๋ฆฌ๊ณ ๋ฌธ์ ๋ง์ง๋ง์ ๋ชจ๋ ํ ๋งํ ๊ฐ ์ต์ด์๋ ์ํ๋ฅผ 0์ผ๋ก ์ถ๋ ฅํด์ผํ๋๋ฐ, ์ด ๊ฒฝ์ฐ๋ ์ ์ธํ๊ณ ์ฝ๋๋ฅผ ์์ฑํ๋ค. ๊ทธ๋์ ๊ฒฝ์ฐ์ ์๋ ๋ค์๊ณผ ๊ฐ์ด 2๊ฐ์ง๋ง ๊ณ ๋ คํ๋ค.
- ํ ๋งํ ๋ฅผ ๋ชจ๋ ์ตํ์ง ๋ชปํ์ ๊ฒฝ์ฐ(BFS๋ฅผ ๋๋ฆฌ๊ณ ๋์จ ๊ฐ์ 0์ด ํฌํจ๋์ด ์๋ ๊ฒฝ์ฐ)
- ๋ชจ๋ ํ ๋งํ ๊ฐ ์ต์๊ฒฝ์ฐ or ํ ๋งํ ๊ฐ ๋ชจ๋ ์ต์ ๋๊น์ง์ ์ต์ ๋ ์ง
ํ์ด ๋ฐฉ๋ฒ์ ๋ค์๊ณผ ๊ฐ๋ค.
- queue๋ฅผ ํจ์ ๋ฐ์ ์ ์ธํ๋ค.
- ๋ชจ๋ ์ขํ๋ฅผ ๊ฒ์ํ์ฌ ์ต์ ํ ๋งํ (1)์ ์ขํ๋ง
queue
์๋ค ์ง์ด ๋ฃ๋๋ค. BFS
ํจ์๋ฅผ ๊ตฌํํ๋ค. (์ด์ ๊ณผ ๋์ผ: ์, ํ, ์ข, ์ฐ ์ ์ธ -> ํ์ฌ ๋ค๋ฅด์ง ์์ ์ขํ ๋ค๋ฅด๊ธฐ -> ์ด์ ์ขํ์ +1์ฉ ๋์ ์ํค๊ธฐ)BFS
์คํ- ์คํํ๊ณ ๋์จ 2์ฐจ์ ๋ฐฐ์ด ์ค
0
์ด ํฌํจ๋์ด ์์ผ๋ฉด-1
์ถ๋ ฅ ์๋๋ฉด 2์ฐจ์ ๋ฐฐ์ด์ ์ต๋๊ฐ์์ -1 ํด์ฃผ๊ธฐ(-1์ ํ๋ ์ด์ ๋ BFS๊ฐ ๋ ์ง๋1(ํ๋ฃจ)
๋ถํฐ ์์๋์ด์ผ ํ๋๋ฐ2(์ดํ)
๋ถํฐ ์์ํ๊ธฐ ๋๋ฌธ์ด๋ค.)
์ต์ ํ ๋งํ ๊ฐ 2๊ฐ ์ด์ ๋ค์ด์๋ ์์ ์
๋ ฅ 3
์ BFS
๋ก ๊ตฌํํ๋ฉด ๋ค์๊ณผ ๊ฐ์ ๊ฒฐ๊ณผ๊ฐ ๋์จ๋ค.
์ขํ๊ฐ์ด 1์ ๋์์ BFS
๋๋ฆฌ๋ ๊ฒ์ด๋ฏ๋ก ์ฒ์ queue
์๋ (0, 0), (3, 5)
๊ฐ ๋ค์ด๊ฐ ์๊ณ ์ดํ ํ๋์ฉ popleft()
ํ๋ฉด์ ๋ค์ ์ขํ๊ฐ 0(์ต์ง ์์ ํ ๋งํ )
์ด๋ฉด ์ด์ ๊ฐ์ +1
์ด ๋์ ๋๋ค.
์ฝ๋๋ฅผ ๊ฐ๊ฒฐํ๊ฒ ์์ฑํ๋ ค๊ณ ์๊พธ ํท๊ฐ๋ฆฌ๋ ๋ฌธ์ฅ์ด ์๋๋ฐ, if graph[i][j] == 1:
์ if graph[i][j]:
๋ ๋ค๋ฅธ ์ฝ๋์ด๊ณ , if not graph[i][j]:
์ if graph[i][j] == 0:
๋ ๊ฐ์ ์ฝ๋์ด๋ค. ๊น๋จน์ง ๋ง์.
import sys
from collections import deque
input = sys.stdin.readline
def bfs():
while queue:
x, y = queue.popleft()
print(x, y)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if not graph[nx][ny]:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
return graph
queue = deque()
m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
for i in range(n):
for j in range(m):
if graph[i][j] == 1:
queue.append((i, j)) # extract ripen tomatoes(value = 1)
result = bfs() # execute bfs ripen tomatoes at the same time
print(result)
if True in map(lambda x: 0 in x, result): # not all ripen tomatoes
print(-1)
else: # all ripen tomatoes or minimum days of ripen tomatoes
print(max(map(max, result))-1)
'Algorithm > ๋ฐฑ์ค(BOJ)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ ํ์ด์ฌ(python) ] ๋ฐฑ์ค 4963 - ์ฌ์ ๊ฐ์(DFS) (0) | 2021.04.20 |
---|---|
[ ํ์ด์ฌ(python) ] ๋ฐฑ์ค 4963 - ์ฌ์ ๊ฐ์(BFS) (0) | 2021.04.20 |
[ ํ์ด์ฌ(python) ] ๋ฐฑ์ค 1926 - ๊ทธ๋ฆผ(BFS) (0) | 2021.04.20 |
[ ํ์ด์ฌ(python) ] ๋ฐฑ์ค 2606 - ๋ฐ์ด๋ฌ์ค(DFS) (0) | 2021.04.19 |
[ ํ์ด์ฌ(python) ] ๋ฐฑ์ค 11724 - ์ฐ๊ฒฐ ์์์ ๊ฐ์(DFS) (0) | 2021.04.19 |
๋๊ธ