백준 11123번 Python / DFS

문제풀이 GitHub

https://github.com/Seokii/baekjoon

GitHub - Seokii/baekjoon: Daily Commit for Baekjoon

깊이 우선 탐색(DFS)

https://seokii.tistory.com/30 

[알고리즘] 깊이 우선 탐색 (DFS, Depth-First Search)이란?

문제 링크

https://www.acmicpc.net/problem/11123

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

 

풀이

import sys
sys.setrecursionlimit(10 ** 6) # 재귀 런타임 에러 해결 코드(허용 깊이를 늘려줌)

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(input())
res = []
temp = []

for _ in range(t):
    cnt = []
    h,w = map(int, input().split())
    graph = [list(map(str, input().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 = []

전형적인 DFS, BFS를 활용한 문제입니다.

DFS 방식으로 문제를 해결했습니다.