
▶ 실버 2 (DFS)

풀이
DFS나 BFS를 이용하여 덩어리 개수를 세면 되는 간단한 문제입니다.
2차원 DFS를 구현하고,
2중 for 문을 이용하여 방문하지 않았고, #이라면 DFS를 실행하여 visited 배열을 갱신해줍니다.
이런 방식으로 덩어리 개수를 세면 됩니다.
그리고 python에서 DFS를 구현할 때는 sys.setrecursionlimit(10**6) 코드를 추가해야한다.
코드
# 11123_양 한마리... 양 두마리...
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
t = int(input())
for _ in range(t):
h, w = map(int, input().split())
garden = [input().split()[0] for _ in range(h)]
visited = [[False for _ in range(w)] for _ in range(h)]
x_dir = [1, -1, 0, 0]
y_dir = [0, 0, 1, -1]
def DFS(x, y):
visited[x][y] = True
for i in range(4):
nx, ny = x + x_dir[i], y + y_dir[i]
if 0 <= nx < h and 0 <= ny < w and not visited[nx][ny] and garden[nx][ny] == '#':
DFS(nx, ny)
return
ans = 0
for i in range(h):
for j in range(w):
if not visited[i][j] and garden[i][j] == '#':
DFS(i, j)
ans += 1
print(ans)
'Algorithm > Baekjoon' 카테고리의 다른 글
20922_겹치는 건 싫어 (0) | 2025.03.09 |
---|---|
14502_연구소 (0) | 2025.03.07 |
15558_점프 게임 (0) | 2025.02.26 |
16719_ZOAC (0) | 2025.02.25 |
5014_스타트링크 (0) | 2025.02.25 |