[baekjoon] 백준 3187번(파이썬): 양치기 꿍

문제

3187번: 양치기 꿍

- 양치기 꿍은 맨날 늑대가 나타났다고 마을 사람들을 속였지만 이젠 더이상 마을 사람들이 속지 않는다.

- 화가 난 꿍은 복수심에 불타 아예 늑대들을 양들이 있는 울타리안에 마구 집어넣어 양들을 잡아먹게 했다.

- 하지만 양들은 보통 양들이 아니다.

- 같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많을 경우 늑대가 전부 잡아먹힌다.

- 물론 그 외의 경우는 양이 전부 잡아먹히겠지만 말이다.

- 꿍은 워낙 똑똑했기 때문에 이들의 결과는 이미 알고있다.

- 만약 빈 공간을 '.'(점)으로 나타내고 울타리를 '#', 늑대를 'v', 양을 'k'라고 나타낸다면 여러분은 몇 마리의 양과 늑대가 살아남을지 계산할 수 있는지 구하는 문제이다.

- 단, 울타리로 막히지 않은 영역에는 양과 늑대가 없으며 양과 늑대는 대각선으로 이동할 수 없다.

-  각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다.

- 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다.

- 살아남게 되는 양과 늑대의 수를 각각 순서대로 출력한다.

알고리즘

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

- 울타리가 아니라면 탐색하여 그때의 모든 문자열을 리스트에 추가한다.

- 추가한 문자열에서 늑대와 양의 수를 비교하여 살아남은 동물의 수를 리스트에 담는다.

- 각 구역에서 살아남은 양과 늑대의 합을 출력한다.

코드

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


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

    if graph[x][y] != "#":

        # 각 구역의 모든 문자열을 추가
        battle.append(graph[x][y])

        # 해당 노드 방문 처리
        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, input())) for _ in range(r)]

# 각 구역에서 누가 살아남았는지 비교하기 위한 리스트
battle = []

# 각 구역에서 승리한 늑대와 양
res_v = []
res_k = []

for i in range(r):
    for j in range(c):
        # 울타리가 아니라면 탐색
        if graph[i][j] != "#":
            dfs(i, j)

            # 각 구역마다 양과 늑대 중 누가 살아남는지 비교
            if battle.count('v') < battle.count('k'):
                res_k.append(battle.count('k'))
            else:
                res_v.append(battle.count('v'))

            # 새로운 구역을 위해 비운다.
            battle = []

# 각 구역에서 승리한 양과 늑대의 합을 출력
print(sum(res_k), sum(res_v))

github

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