[๋ฐฑ์ค] 2636 ์น์ฆ with Python
๐ BOJ 2636 ์น์ฆ
๐ก ์กฐ๊ฑด
์ ์ฌ๊ฐํ ์นธ๋ค๋ก ์ด๋ฃจ์ด์ง ์ฌ๊ฐํ ๋ชจ์์ ํ์ด ์๊ณ , ๊ทธ ์์ ์์ ์น์ฆ๊ฐ ๋์ฌ ์๋ค.
์น์ฆ๋ฅผ ๊ณต๊ธฐ ์ค์ ๋์ผ๋ฉด ๋ น๊ฒ ๋๋๋ฐ ๊ณต๊ธฐ์ ์ ์ด๋ ์นธ์ ํ ์๊ฐ์ด ์ง๋๋ฉด ๋ น์ ์์ด์ง๋ค.
์น์ฆ์ ๊ตฌ๋ฉ ์์๋ ๊ณต๊ธฐ๊ฐ ์์ง๋ง ๊ตฌ๋ฉ์ ๋๋ฌ์ผ ์น์ฆ๊ฐ ๋ น์์ ๊ตฌ๋ฉ์ด ์ด๋ฆฌ๋ฉด ๊ตฌ๋ฉ ์์ผ๋ก ๊ณต๊ธฐ๊ฐ ๋ค์ด๊ฐ๊ฒ ๋๋ค.์ ๋ ฅ์ผ๋ก ์ฌ๊ฐํ ๋ชจ์์ ํ์ ํฌ๊ธฐ์ ํ ์กฐ๊ฐ์ ์น์ฆ๊ฐ ํ ์์ ์ฃผ์ด์ก์ ๋,
๊ณต๊ธฐ ์ค์์ ์น์ฆ๊ฐ ๋ชจ๋ ๋ น์ ์์ด์ง๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ๊ณผ ๋ชจ๋ ๋ น๊ธฐ ํ ์๊ฐ ์ ์ ๋จ์์๋ ์น์ฆ์กฐ๊ฐ์ด ๋์ฌ ์๋ ์นธ์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ธ๋ก์ ๊ฐ๋ก์ ๊ธธ์ด๋ ์ต๋ 100์ด๋ค.
์น์ฆ๊ฐ ์๋ ์นธ์ 0, ์น์ฆ๊ฐ ์๋ ์นธ์ 1๋ก ์ฃผ์ด์ง๋ฉฐ ๊ฐ ์ซ์ ์ฌ์ด์๋ ๋น์นธ์ด ํ๋์ฉ ์๋ค.
๋๋น์ฐ์ ํ์, BFS ์ ํ์ ๋ฌธ์
๐ฅ ์์ค ์ฝ๋
from collections import deque
from sys import stdin
n, m = map(int, stdin.readline().split())
board = []
for _ in range(n):
board.append(list(map(int, stdin.readline().split())))
dx, dy = [1, 0, 0, -1], [0, 1, -1, 0]
ans = 0
cnt = 0
def melt():
cnt = 0
for i in range(n):
for j in range(m):
if board[i][j] == -1:
cnt += 1
board[i][j] = 0
return cnt
def bfs():
global ans, cnt
q = deque()
q.append((0, 0))
visited = set()
visited.add((0, 0))
while q:
x, y = q.popleft()
for i in range(4):
nx, ny = dx[i] + x, dy[i] + y
if -1 < nx < n and -1 < ny < m:
if (nx, ny) not in visited:
if board[nx][ny] == 0:
q.append((nx, ny))
visited.add((nx, ny))
elif board[nx][ny] == 1:
board[nx][ny] = -1
melt_cnt = melt()
if melt_cnt != 0:
cnt = melt_cnt
else:
print(ans)
print(cnt)
exit()
while 1:
bfs()
ans += 1
๐ ์์ ๋ฐ ์คํ๊ฒฐ๊ณผ
์์
13 12
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0
0 1 1 1 0 0 0 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0 0 0
0 1 1 1 1 1 0 1 1 0 0 0
0 1 1 1 1 0 0 1 1 0 0 0
0 0 1 1 0 0 0 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
์คํ๊ฒฐ๊ณผ
3
5
โจ๏ธ ๋ฌธ์ ํ์ด
BFS ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ์ฌ ์ขํ ์ด๋์ ํ๋ฉฐ ๋น๊ณต๊ฐ๊ณผ ์น์ฆ๋ฅผ ์ ๋ ฅ๋ฐ์ board ์์ ์น์ฆ๋ฅผ ์ฐพ์ ํ์๋ฅผ ํ ๋ค, ๋ น์๋ค๊ณ ์ฒ๋ฆฌํ๋ ๊ฒ์ด ๋ชฉํ์ ๋๋ค.
์น์ฆ๊ฐ ๋ชจ๋ ๋ น์ ๋๊น์ง BFS ์๊ณ ๋ฆฌ์ฆ์ ํธ์ถํด์ผํ๊ธฐ์ while ๋ก ํธ์ถํด์ฃผ๋ฉด์ ํธ์ถํ ํ์๋ฅผ ans์ ์ ์ฅํด์ค๋๋ค.์ด ๋ฌธ์ ๋ ์น์ฆ ์๋ฅผ ๊ฑท๋ ๋๋์ด ์๋, ๋น ๊ณต๊ฐ์ ๊ฑธ์ผ๋ฉด์ ์น์ฆ๊ฐ ์๋ ๊ณณ์ ํ์ํ์ฌ ์ฒ๋ฆฌํ๋ ๋ฌธ์ ์ ๋๋ค.
(2)๋ฒ๊ณผ ๊ฐ์ด ์ฒ๋ฆฌํ์ง ์์ผ๋ฉด ์น์ฆ์ ๊ฒ๋ง ์ฒดํฌํด์ค ์ ์์ต๋๋ค.
์ฒดํฌ๋ ์น์ฆ๋ฅผ ๋ น์ด๋ ํจ์์ธ melt() ๋ฅผ ์ ์ํ์ฌ ํธ์ถํ์ต๋๋ค.
melt() ํจ์๋ฅผ ํธ์ถํ๊ณ ๋ฐํ๋ฐ์ ๊ฐ์ ์น์ฆ๊ฐ ๋ น์ ๊ฐ์์ ๋๋ค.
๋ชจ๋ ๋ น๊ธฐ ํ์๊ฐ ์ ์ ์น์ฆ๊ฐ ๋ น์ ๊ฐ์๋ฅผ ์ถ๋ ฅํด์ผํ๋, ๋ฐํ๋ ๊ฐ์ cnt ๋ผ๋ ๋ณ์์ ์ ์ฅํด์ค๋๋ค.๋ น์ง ์์๋ค๋ฉด ๊ทธ๋๋ก ans, cnt ๋ฅผ ์ถ๋ ฅํด์ค๋๋ค.
๐พ ๋๋์
- ๋น๊ณต๊ฐ์ ๊ฑธ์ผ๋ฉฐ ์น์ฆ์ ๋ฒฝ๋ฉด์ ํ๋๋ค๋ ๋๋์ ์ป๊ธฐ ์ด๋ ค์ ๋ค.