๐Ÿ˜Š ๋ฐฑ์ค€ 2667 : ๋‹จ์ง€๋ฒˆํ˜ธ๋ถ™์ด๊ธฐ

6145 ๋‹จ์–ด DFSBFSalgorithmbaekjoonpythonBFS

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

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ