[baekjoon] 백준 11123번(파이썬): 양 한마리... 양 두마리...

문제

11123번: 양 한마리... 양 두마리...

알고리즘

- dfs 탐색을 통해 문제를 수행한다.

- 케이스만큼 반복하여 양의 무리를 출력한다.

코드

import sys
sys.setrecursionlimit(10 ** 6) # 재귀 허용 깊이를 수동으로 늘려주는 코드


# dfs 탐색
def dfs(x, y):
    
    if x <= -1 or x >= h or y <= -1 or y >= w:
        return False

    # 탐색하지 않았다면 탐색
    if graph[x][y] == "#":
        # 탐색 확인
        graph[x][y] = "."
        # 양의 수를 확인
        cnt.append(1)

        # 상/하/좌/우를 재귀적으로 탐색
        dfs(x + 1, y)
        dfs(x - 1 , y)
        dfs(x, y + 1)
        dfs(x, y - 1)

        return True
    return False


t = int(sys.stdin.readline())
res = []
temp = []
# 케이스만큼 반복
for _ in range(t):
    cnt = []
    h, w = map(int, sys.stdin.readline().split())
    graph = [list(map(str, sys.stdin.readline().strip())) for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if graph[i][j] == "#":
                dfs(i, j)
                temp.append(len(cnt))
                cnt = []
    # 양의 무리 수를 출력
    print(len(temp))
    temp = []

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법