[BOJ/백준] 3184번 양 (Python 파이썬)

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

3184번: 양

 

문제

미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다.

마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다.

한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서 "탈출"할 수 있는 칸은 어떤 영역에도 속하지 않는다고 간주한다.

다행히 우리의 양은 늑대에게 싸움을 걸 수 있고 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아낸다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.

맨 처음 모든 양과 늑대는 마당 안 영역에 존재한다.

아침이 도달했을 때 살아남은 양과 늑대의 수를 출력하는 프로그램을 작성하라.

입력

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

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

출력

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

예제 입력 1

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

예제 출력 1

0 2

예제 입력 2

8 8
.######.
#..o...#
#.####.#
#.#v.#.#
#.#.o#o#
#o.##..#
#.v..v.#
.######.

예제 출력 2 

3 1

예제 입력 3 

9 12
.###.#####..
#.oo#...#v#.
#..o#.#.#.#.
#..##o#...#.
#.#v#o###.#.
#..#v#....#.
#...v#v####.
.####.#vv.o#
.......####.

예제 출력 3 

3 5

 

---

풀이

우선 문제 유형은 이전에 풀이했던 영역 탐색 종류의 문제들과 유사합니다. 하지만 크게 2가지 차이점이 있습니다.

1. 탐색한 결과에 따라서 상태를 관리해야 한다. (상태: 양과 늑대의 마릿수 + 승부 결과)
2. 숫자가 아닌 문자을 다룬 미로

문제의 상황을 정리하면 다음과 같습니다.

울타리 내부에 양과 늑대가 여러 마리 존재할 수 있고, 만약 양이 늑대보다 많다면 늑대를 울타리 내부에서 쫓아내고, 그렇지 않은 경우에는 해당 울타리 내 양들이 모두 늑대에게 잡아먹힌다.

따라서, 각 울타리 내부를 탐색할 때 다음의 동작을 수행해야 합니다.
(1) 양과 늑대의 마릿수를 각각 count한다.
(2) 숫자를 비교하여 승부 결과를 채점하여 해당 울타리 내부의 최종 양과 늑대의 마릿수를 정한다.

이와 같이 모든 울타리 내부 영역을 탐색한 후, 모든 양과 늑대의 마릿수를 출력하면 됩니다.

 

이를 위해 저는 다음과 같은 흐름으로 문제를 풀이했습니다.

def solve():
    total_sheep, total_wolf = 0, 0
    for x in range(C):
        for y in range(R):
            if graph[y][x] != '#' and not visited[y][x]:
                sheep, wolf = BFS(x, y) # 울타리 내부를 탐색한다.

                # 해당 울타리 영역 내에서 양이 늑대보다 수가 많다면 이긴다.
                if sheep > wolf:
                    wolf = 0
                # 그렇지 않다면 모두 잡아먹힌다.
                else:
                    sheep = 0
                total_sheep += sheep
                total_wolf += wolf
    print(total_sheep, end=' ')
    print(total_wolf, end=' ')

우선, 모든 구역을 돌면서 해당 지점이 울타리 ('#')가 아니라면 울타리 내부라는 뜻이므로, 탐색을 시작합니다.

탐색의 결과로는 양과 늑대의 마릿수를 리턴합니다. 

이제 서로의 마릿수를 비교하여 양이 늑대보다 많다면 늑대의 마릿수를 0으로 조정합니다. 이것의 의미는, 방금 탐색을 마친 울타리 내부 영역에서의 늑대를 모두 쫓아냈다는 뜻이 됩니다. (모든 늑대의 마릿수가 아닙니다.)

만약 그렇지 않다면 양의 마릿수를 0으로 조정합니다.

이를 반복하여 모든 울타리 내부 영역을 탐색하면 문제 풀이가 완료됩니다.

또한, 주의할 점은 BFS로 탐색을 시작할 때, 시작점의 경우의 수는 (1) 빈 곳 (2) 양 (3) 늑대 이렇게 3가지가 있으므로 이에 대한 마릿수 상태 관리도 필요합니다.

아래는 최종적인 코드입니다.

 

Code

import sys
from collections import deque
input = sys.stdin.readline
R, C = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(R)]
visited = [[False for _ in range(C)] for _ in range(R)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 울타리 내부를 BFS 실시
# 양과 늑대의 마리 수를 저장한다. -> 결과 계산


def BFS(x, y):
    queue = deque([(x, y)])
    visited[y][x] = True
    sheep, wolf = 0, 0

    # 탐색 시작 점 -> 양 or 늑대 확인
    if graph[y][x] == 'o':
        sheep += 1
    elif graph[y][x] == 'v':
        wolf += 1

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            next_x, next_y = x + dx[i], y + dy[i]
            if 0 <= next_x < C and 0 <= next_y < R:  # 범위 확인
                if not visited[next_y][next_x] and graph[next_y][next_x] != '#':  # 탐색 가능 확인
                    queue.append([next_x, next_y])
                    visited[next_y][next_x] = True
                    # 양 or 늑대에 따라 마리 수 증가
                    if graph[next_y][next_x] == 'o':
                        sheep += 1
                    elif graph[next_y][next_x] == 'v':
                        wolf += 1
    return (sheep, wolf)


def solve():
    total_sheep, total_wolf = 0, 0
    for x in range(C):
        for y in range(R):
            if graph[y][x] != '#' and not visited[y][x]:
                sheep, wolf = BFS(x, y)

                # 해당 울타리 영역 내에서 양이 늑대보다 수가 많다면 이긴다.
                if sheep > wolf:
                    wolf = 0
                # 그렇지 않다면 모두 잡아먹힌다.
                else:
                    sheep = 0
                total_sheep += sheep
                total_wolf += wolf
    print(total_sheep, end=' ')
    print(total_wolf, end=' ')


solve()