๐ง ์น์ฆ
๋ฐฑ์ค Class4 Gold3
solved_ac[Class4] ์น์ฆ
๋ฌธ์
<๊ทธ๋ฆผ 1>
NรM์ ๋ชจ๋์ข ์ด ์์ ์์ฃผ ์์ ์น์ฆ๊ฐ <๊ทธ๋ฆผ 1>๊ณผ ๊ฐ์ด ํ์๋์ด ์๋ค. ๋จ, N ์ ์ธ๋ก ๊ฒฉ์์ ์์ด๊ณ , M ์ ๊ฐ๋ก ๊ฒฉ์์ ์์ด๋ค. ์ด ์น์ฆ๋ ๋๋ ๋ณด๊ด์ ํด์ผ๋ง ํ๋๋ฐ ์ค๋ด์จ๋์ ๋ด์ด๋์ผ๋ฉด ๊ณต๊ธฐ์ ์ ์ดํ์ฌ ์ฒ์ฒํ ๋ น๋๋ค. ๊ทธ๋ฐ๋ฐ ์ด๋ฌํ ๋ชจ๋์ข ์ด ๋ชจ์์ ์น์ฆ์์ ๊ฐ ์น์ฆ ๊ฒฉ์(์ ์ ์ ์ฌ๊ฐํ ๋ชจ์)์ 4๋ณ ์ค์์ ์ ์ด๋ 2๋ณ ์ด์์ด ์ค๋ด์จ๋์ ๊ณต๊ธฐ์ ์ ์ดํ ๊ฒ์ ์ ํํ ํ์๊ฐ๋ง์ ๋ น์ ์์ด์ ธ ๋ฒ๋ฆฐ๋ค. ๋ฐ๋ผ์ ์๋ <๊ทธ๋ฆผ 1> ๋ชจ์๊ณผ ๊ฐ์ ์น์ฆ(ํ์์ผ๋ก ํ์๋ ๋ถ๋ถ)๋ผ๋ฉด C๋ก ํ์๋ ๋ชจ๋ ์น์ฆ ๊ฒฉ์๋ ํ ์๊ฐ ํ์ ์ฌ๋ผ์ง๋ค.
<๊ทธ๋ฆผ 2>
<๊ทธ๋ฆผ 3>
<๊ทธ๋ฆผ 2>์ ๊ฐ์ด ์น์ฆ ๋ด๋ถ์ ์๋ ๊ณต๊ฐ์ ์น์ฆ ์ธ๋ถ ๊ณต๊ธฐ์ ์ ์ดํ์ง ์๋ ๊ฒ์ผ๋ก ๊ฐ์ ํ๋ค. ๊ทธ๋ฌ๋ฏ ๋ก ์ด ๊ณต๊ฐ์ ์ ์ดํ ์น์ฆ ๊ฒฉ์๋ ๋ น์ง ์๊ณ C๋ก ํ์๋ ์น์ฆ ๊ฒฉ์๋ง ์ฌ๋ผ์ง๋ค. ๊ทธ๋ฌ๋ ํ ์๊ฐ ํ, ์ด ๊ณต๊ฐ์ผ๋ก ์ธ๋ถ๊ณต๊ธฐ๊ฐ ์ ์ ๋๋ฉด <๊ทธ๋ฆผ 3>์์์ ๊ฐ์ด C๋ก ํ์๋ ์น์ฆ ๊ฒฉ์๋ค์ด ์ฌ๋ผ์ง๊ฒ ๋๋ค.
๋ชจ๋์ข ์ด์ ๋งจ ๊ฐ์ฅ์๋ฆฌ์๋ ์น์ฆ๊ฐ ๋์ด์ง ์๋ ๊ฒ์ผ๋ก ๊ฐ์ ํ๋ค. ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง ์น์ฆ๊ฐ ๋ชจ๋ ๋ น์ ์์ด์ง๋๋ฐ ๊ฑธ๋ฆฌ๋ ์ ํํ ์๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์๋ ๋ชจ๋์ข ์ด์ ํฌ๊ธฐ๋ฅผ ๋ํ๋ด๋ ๋ ๊ฐ์ ์ ์ N, M (5 โค N, M โค 100)์ด ์ฃผ์ด์ง๋ค. ๊ทธ ๋ค์ N๊ฐ์ ์ค์๋ ๋ชจ๋์ข ์ด ์์ ๊ฒฉ์์ ์น์ฆ๊ฐ ์๋ ๋ถ๋ถ์ 1๋ก ํ์๋๊ณ , ์น์ฆ๊ฐ ์๋ ๋ถ๋ถ์ 0์ผ๋ก ํ์๋๋ค. ๋ํ, ๊ฐ 0๊ณผ 1์ ํ๋์ ๊ณต๋ฐฑ์ผ๋ก ๋ถ๋ฆฌ๋์ด ์๋ค.
์ถ๋ ฅ
์ถ๋ ฅ์ผ๋ก๋ ์ฃผ์ด์ง ์น์ฆ๊ฐ ๋ชจ๋ ๋ น์ ์์ด์ง๋๋ฐ ๊ฑธ๋ฆฌ๋ ์ ํํ ์๊ฐ์ ์ ์๋ก ์ฒซ ์ค์ ์ถ๋ ฅํ๋ค.
์์ ์ ๋ ฅ 1
8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
์์ ์ถ๋ ฅ 1
4
๐ ๊ณผ์ ์ค๊ณ
์ค๋ช ํ๊ธฐ์ ์์ ๋๋ ๊ธฐ๋ณธ BFS ํ์ ์กฐ๊ฑด๋ง ์ถ๊ฐํ์ฌ ํ์๋ค.
๋ฒฝ ๋ถ์๊ณ ์ด๋ํ๊ธฐ์ ๋น์ทํ ๊ฒฐ์ ๋ฌธ์ ์ด๋ค.
์์ ๋ฅผ ์๊ฐ์ ๊ฒฝ๊ณผ์ ๋ฐ๋ผ ๋ํ๋ด๋ณด์๋ค.
(0,0) ์ด๋ก์ ํ๊ดํ ์ง์ ์ ์์ ๋ ธ๋๋ก ์ค์ ํ์๋ค. ์น์ฆ์ ํ๊ธฐ๋์ด ์๋ ํ๋์ ์ซ์๋ ์น์ฆ๊ฐ ๋ช ๊ฐ์ ์ธ๋ถ ๊ณต๊ธฐ์ ๋ง๋ฟ์ ์๋์ง๋ฅผ ์๋ฏธํ๋ค.
์ฆ, ์ธ๋ถ ๊ณต๊ธฐ(0) ๊ธฐ์ค์ผ๋ก ์ํ์ข์ฐ ํ์์ ํ๋ฉฐ ์น์ฆ(1)๋ฅผ ๋ง๋ ๋๋ง๋ค ํฐ์น ์นด์ดํธ๋ฅผ ์ฆ๊ฐ์ํจ๋ค.
๊ทธ๋ ๊ฒ ํ์ ๋, ์ธ๋ถ ๊ณต๊ธฐ์ ํฐ์น ์นด์ดํธ๊ฐ 2๋ฒ ์ด์๋ ์น์ฆ๋ง ๊ณจ๋ผ์ ๋ น์ธ๋ค(1์ 0์ผ๋ก ๋ฐ๊พผ๋ค.)
์ถ๋ฐ ๋ ธ๋์์ BFS๋ฅผ ๋๋ฆฐ ๋ค์์ ๋ ์ด์ ๋จ์์๋ ์น์ฆ๊ฐ ์์ ๋๊น์ง BFS๋ฅผ ๋ฐ๋ณตํ๋ค.
๋์์ BFS๋ฅผ ํ ๋ฒ ๋๋ฆด ๋๋ง๋ค ์๊ฐ์ ์ฆ๊ฐ์์ผ์ฃผ๋ฉด(hour += 1) ์ต์ข ์ ์ธ ์น์ฆ๊ฐ ๋ น๋ ์๊ฐ์ ๊ตฌํ ์ ์๋ค.
๐จ๐ปโ๐ป CODE
from collections import deque
N,M = map(int,input().split())
cheese = []
for _ in range(N):
cheese.append(list(map(int,input().split())))
dx = [1,-1,0,0]
dy = [0,0,1,-1]
def bfs(a,b):
q = deque([(a,b)])
visited = [[0]*M for _ in range(N)]
touch = [[0]*M for _ in range(N)]
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<M and visited[nx][ny] == 0:
if cheese[nx][ny] == 0:
q.append((nx,ny))
visited[nx][ny] = 1
if cheese[nx][ny] == 1:
touch[nx][ny] += 1
for i in range(N):
for j in range(M):
if touch[i][j] >= 2:
cheese[i][j] = 0
def empty_check(cheese):
for i in range(N):
for j in range(M):
if cheese[i][j] == 1:
return False
return True
hour = 0
while True:
if empty_check(cheese):
print(hour)
break
bfs(0,0)
hour += 1