[Baekjoon/๐ฅSilverโ ก] 4963: ์ฌ์ ๊ฐ์
Intro
์ ๊ทผ ๋ฐฉ๋ฒ๐โโ๏ธ
-
ํด๋น ๋ฌธ์ ๋ ๋จ์ํ ์ํ์ข์ฐ๋ง์ด ์๋ ๋๊ฐ์ ๊น์ง ํฌํจํด bfs, dfs๋ฅผ ์ ์ฉํ๋ ๋ฌธ์ ์ด๋ค.
-
ํ๋ ฌ๋ก ์ฃผ์ด์ง๋ ๊ทธ๋ํ์์ ๋๊ฐ์ , ์ํ์ข์ฐ๋ฅผ ๋ชจ๋ ํ์ธํ๊ธฐ ์ํด์๋ ๋ค์์ ๋ฐฐ์ด๋ค์ด ํ์ํ๋ค.
- dx = [-1, 0, 1, -1, 1, -1, 0, 1]
- dy = [-1, -1, -1, 0, 0, 1, 1, 1]
Algoritm๐ฉโ๐ป: BFS
- ์ฐ์ BFS๋ฅผ ์ ์ฉํด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํด๋ณด์.
# 21.01.10
# 4963: ์ฌ์ ๊ฐ์
import sys
dx = [-1, 0, 1, -1, 1, -1, 0, 1]
dy = [-1, -1, -1, 0, 0, 1, 1, 1]
def bfs(i, j):
lst[i][j] = 0
queue = [[i, j]]
while queue:
a, b = queue[0][0], queue[0][1]
del queue[0]
for k in range(8):
x = a + dx[k]
y = b + dy[k]
if 0 <= x < h and 0 <= y < w and lst[x][y] == 1:
lst[x][y] = 0
queue.append([x, y])
while 1:
w, h = map(int, sys.stdin.readline().rstrip().split())
if w == 0 and h == 0:
break
lst = []
for i in range(h):
lst.append(list(map(int, sys.stdin.readline().rstrip().split())))
cnt = 0
for i in range(h):
for j in range(w):
if lst[i][j] == 1:
bfs(i, j)
cnt += 1
print(cnt)
-
๋ชจ๋ ํ๋ ฌ์ ๋๋ฉฐ 1์ธ ์์์ ๋ํด์ BFS๋ฅผ ํธ์ถํ๋ค.
-
BFS ํจ์์์๋ ํด๋น ์์์ ๋๊ฐ์ , ์ํ์ข์ฐ์ ์กด์ฌํ๋ ์์๋ค ์ค ๊ฐ์ด 1์ธ ์์๋ค์ ์ฐจ๋ก๋ก queue์ ๋ฃ์ผ๋ฉด์ ๊ทธ ๊ฐ๋ค์ 0์ผ๋ก ๋ฐ๊พผ๋ค.
-
1์ธ ์์์ ๋๊ฐ์ , ์ํ์ข์ฐ์ ์๋ ๊ฐ์ด 1์ธ ์์๋ค์ ํ๋์ ์ฌ์ผ๋ก ์ทจ๊ธ๋๊ธฐ ๋๋ฌธ์ด๋ค.
-
BFS์์ ๋ฐํ๋ ํ, ์ฌ์ ๊ฐ์๋ฅผ ํ๋ ์ฆ๊ฐ์์ผ์ค๋ค.
-
-
๋ชจ๋ ์์๋ค์ ์ํํ ํ, ์ฌ์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
Algoritm๐ฉโ๐ป: DFS
- ์ด๋ฒ์๋ ํด๋น ๋ฌธ์ ๋ฅผ DFS๋ฅผ ํตํด์ ํด๊ฒฐํด๋ณด์.
# 21.01.10
# 4963: ์ฌ์ ๊ฐ์
import sys
sys.setrecursionlimit(10000)
dx = [-1, 0, 1, -1, 1, -1, 0, 1]
dy = [-1, -1, -1, 0, 0, 1, 1, 1]
def dfs(i, j):
lst[i][j] = 0
for k in range(8):
x = i + dx[k]
y = j + dy[k]
if 0 <= x < h and 0 <= y < w and lst[x][y] == 1:
dfs(x, y)
while 1:
w, h = map(int, sys.stdin.readline().rstrip().split())
if w == 0 and h == 0:
break
lst = []
for i in range(h):
lst.append(list(map(int, sys.stdin.readline().rstrip().split())))
cnt = 0
for i in range(h):
for j in range(w):
if lst[i][j] == 1:
dfs(i, j)
cnt += 1
print(cnt)
โ ์ ๊น๐: โsys.setrecursionlimit(10000)โ
- ํ์ด์ฌ์ ๊ธฐ๋ณธ ์ฌ๊ท ๊น์ด ์ ํ์ด 1000์ผ๋ก ๋งค์ฐ ์๋ค.
-
์ฌ๊ท๋ฅผ ์ฌ์ฉํด ํธ๋ ๋ฌธ์ ์ผ ๊ฒฝ์ฐ, ์ ์ฝ๋๋ฅผ ํตํด ์ฌ๊ท ์ ํ์ ๊ฑธ๋ฆฌ์ง ์๋๋ก ํด์ผ ํ๋ค!!
-
๋ชจ๋ ํ๋ ฌ์ ๋๋ฉฐ 1์ธ ์์์ ๋ํด์ DFS๋ฅผ ํธ์ถํ๋ค.
-
DFS ํจ์์์๋ ํด๋น ์์์ ๊ฐ์ 0์ผ๋ก ๋ฐ๊พผ ํ, ๋๊ฐ์ ๊ณผ ์ํ์ข์ฐ์ ์๋ ์์๋ค ์ค ๊ฐ์ด 1์ธ ์์๋ค์ ๋ํด์ DFS๋ฅผ ์ฌ๊ท ํธ์ถํ๋ค.
- ๋ชจ๋ ์์๋ค์ ์ํํ ํ, ์ฌ์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
์ฐธ๊ณ ๐
- https://fuzzysound.github.io/sys-setrecursionlimit
- https://velog.io/@hamfan524/%EB%B0%B1%EC%A4%80-4963%EB%B2%88-Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC
- https://pacific-ocean.tistory.com/273
๊ทธ๋ผ!! ์ด๋ฒ ํฌ์คํ ์ ์ฌ๊ธฐ์!
๋!! ~(หโพห~)
๋๊ธ๋จ๊ธฐ๊ธฐ