[baekjoon] 백준 3184번(파이썬): 양

문제

3184번: 양

알고리즘

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

- 재귀 허용 깊이를 늘리지 않으면 런타임 에러가 나올 수 있다.

[baekjoon] 백준 16956번(파이썬): 늑대와 양

- 위 문제와 비슷한 내용이지만 위 문제는 bfs로 풀었고, 이번에는 dfs 탐색을 통해 풀었다.

- 각 영역의 있는 양의 수와 늑대의 수를 비교하고 이긴 동물의 수를 카운트한다.

코드

import sys
sys.setrecursionlimit(10 ** 6)  # 재귀 허용 깊이를 수동으로 늘려주는 코드
# 재귀 허용 깊이를 늘리지 않으면 런타임 에러가 나올 수 있음.


# dfs 탐색
def dfs(x, y):

    if -1 >= x or x >= r or -1 >= y or y >= c:
        return False

    # 울타리가 아니라면
    if graph[x][y] != '#':
        
        # 늑대의 개수 체크
        if graph[x][y] == 'v':
            v.append(1)
        # 양의 개수 체크
        elif graph[x][y] == 'o':
            o.append(1)
        
        graph[x][y] = '#'

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


r, c = map(int, sys.stdin.readline().split())

# 그래프 표현
graph = [list(map(str, sys.stdin.readline().strip())) for _ in range(r)]

o = [] # 각 구역의 있는 양
v = [] # 각 구역의 있는 늑대

sheep = 0 # 살아남은 양
wolf = 0 # 살아남은 늑대

for i in range(r):
    for j in range(c):
        # 울타리가 아니라면 dfs 탐색
        if graph[i][j] != '#':
            dfs(i, j)
            
            # 각 영역을 탐색후 늑대의 수가 양보다 같거나 크면 살아남은 늑대에 더해준다.
            if len(v) >= len(o):
                wolf += len(v)
                
            # 반대로 양의 수가 크면 살아있는 양에 더해준다.
            else:
                sheep += len(o)
                
            # 각 구역의 양과 늑대의 수를 초기화
            v = []
            o = []

print(sheep, wolf)

github

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