문제

입력

첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다.

다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다.

출력

하나의 줄에 아침까지 살아있는 양과 늑대의 수를 의미하는 두 정수를 출력한다.

입력 예시 1

6 6
...#..
.##v#.
#v.#.#
#.o#.#
.###.#
...###

출력 예시 1

0 2

문제 이해

오랜만에 푸는 생각의 전환이 필요한 DFS문제이다. DFS문제는 로직이 똑같을 정도로 비슷한 유형이 많았는데 이번 문제는 좀 참신하고 재밌었다. 총 4개 종류의 문자로 입력이 주어지고, 그 안에서 조건문을 써서 값을 처리해주면 된다.

하나의 울타리 안에서 양과 늑대의 수를 세고, 양이 더 많을 경우만 양의 수를 카운트 해주면 된다. 그외에는 다 잡아먹히기 때문에.

그러면 울타리 구분을 어떻게 해야할까? 처음에 메인에서 DFS를 호출할때, permission이라는 값에 "#"을 제외한 값을 넣고, 그 안에 있는 값이면 DFS를 호출하면 된다. 재호출을 할때도 "v,o,." 이 세가지에 대해서만 호출하면 하나의 울타리만 탐색할 수 있고, 메인에서 한번 호출이 끝났을때의 늑대와 양의 값을 비교해서 값을 카운트 하면 된다.

코드

# 백준 3184번 양

# 떠오른 풀이
"""
 늑대나 양, 빈 공간을 발견하면 메인에서 DFS호출
 상하좌우를 살피면서 방문하지 않았고, #이 아니면 재호출.
 한번의 메인 호출이 끝나면 양과 늑대 수를 비교해서 다른 값에 넣어주고
 원래 늑대와 양을 카운트했던 변수는 0으로 초기화
"""

# 재귀 횟수, 읽는 속도 늘리기
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 방향벡터 동-서-남-북순
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def DFS(y, x, type):
    global visited, backyard, wolf_cnt, sheep_cnt
    visited[y][x] = True

    # 카운트
    if type == "v":
        wolf_cnt += 1
    elif type == "o":
        sheep_cnt += 1
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < C and 0 <= ny < R and backyard[ny][nx] in permission and not visited[ny][nx]:
            DFS(ny, nx, backyard[ny][nx])

# 0. 입력 및 초기화
R, C = map(int, input().split()) #R세로 C가로
visited = [[False] * C for _ in range(R)]
backyard = []
living_wolf = 0
living_sheep = 0

# 메인에서 호출할때 "#"제외 나머지는 통과
permission = [".", "v", "o"]

# 1. 연결 정보 입력
for i in range(R):
    backyard.append(list(input().rstrip()))
# 이중 리스트로 만들어야하기 때문에 list함수를 사용

# 2. DFS호출
for i in range(R):
    for j in range(C):
        if backyard[i][j] in permission and not visited[i][j]:
            wolf_cnt = 0
            sheep_cnt = 0
            DFS(i, j, backyard[i][j])

            # 늑대보다 양이 더 많으면 양 카운트
            if sheep_cnt > wolf_cnt:
                living_sheep += sheep_cnt
            else: # 그 외에는 늑대만 카운트
                living_wolf += wolf_cnt
            

# 3. 출력
print(living_sheep, living_wolf)

참고로 백준의 3187번은 이 문제와 완전 똑같다.
https://www.acmicpc.net/problem/3187