๐ ๋ฐฑ์ค 2667 : ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ
DFS/BFS
๋ค ๋ฒ์งธ ๋ฌธ์ !
๋๋น๋ ์๊ณ ๋ฆฌ์ฆ ๊ฐ์๋ฅผ ๋ฃ๊ณ ํ์๋ค.
๊ฐ์์ ๋์จ ๋ฌธ์ ์ ํ๊ณผ ๋์ผํด์ ๊ฐ๋จํ๊ฒ ํ์๋ค.
๐ Try 1
def dfs(x, y):
if x < 0 or x >= N or y < 0 or y >= N:
return 0
if graph[x][y] == 1:
graph[x][y] = 0
return 1 + dfs(x-1, y) + dfs(x+1, y) + dfs(x, y-1) + dfs(x, y+1)
return 0
N = int(input())
graph, result = [], []
for _ in range(N):
graph.append(list(map(int, input())))
for i in range(N):
for j in range(N):
if graph[i][j] == 1:
result.append(dfs(i, j))
print(len(result))
for x in sorted(result):
print(x)
dfs
๋ฅผ ์ฌ๊ท๋ก ๊ตฌํํ์ฌ ํ์๋ค.
graph
ํํ๋ double-list
์ด๋ค.
๐ Reference
- ๋๋น๋ ์ด์ฝํ
๊ฐ์ 3๊ฐ
https://www.youtube.com/watch?v=7C9RgOcvkvo
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ(๐ ๋ฐฑ์ค 2667 : ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@_3juhwan/๋ฐฑ์ค-2667-๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค