Python으로 푸는 백준 3184. 양

문제의 조건에 따라 하루가 지났을 때,

영역 안에 살아 남아있는 양과 늑대의 수를 출력하는 코드를 짜시오.

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

github에서 코드 보기

문제 조건

- 영역 안의 양의 수가 늑대의 수보다 적으면,  늑대가 그 지역 안의 모든 양을 잡아 먹는다.

- 영역 안의 양의 수가 늑대의 수보다 많으면 양이 이긴다. 이럴 경우 늑대가 죽는다. (주의)

문제 풀이

문제의 조건에서 주의할 점은 양이 늑대와 싸워서 이길 경우에는, 늑대가 죽는다는 점이다. 문제 조건에서 단순히 '이긴다' 라고만 표시가 되어 있어서, 늑대와 양이 대치 상태로 끝날 줄 알고 늑대의 수를 차감시켜주지 않았더니 결과값이 틀리게 나왔다. 이 부분만 코드에 추가하면 문제는 쉽게 풀린다.  알고리즘은 다음과 같다. BFS를 활용하면 문제는 풀린다.

방문 여부를 표시하기 위해 visted 2차원 배열을 만든다.

1. 방문하지 않은 늑대를 찾아서 순회한다. 

• 순회하면서 전체 양과 늑대의 수를 계산한다.

2. 늑대를 발견하면, 늑대가 울타리 내 이동 가능한 모든 영역을 탐색한다.

• 빈 필드나 양와 늑대를 만나면 방문 여부를 표시한다.

•  늑대가 양을 만나면 양의 수를 증가시킨다.

•  늑대를 만나면, 늑대의 수를 증가시킨다.

3. 모든 이동 가능 영역을 탐색했다면 늑대의 수와 양의 수를 체크해서 전체 양과 늑대의 수에서 차감시킨다.

파이썬 코드

import sys
input = sys.stdin.readline
 
 
def solve(n, m, field):
    visited = [[False] * m for j in range(n)]
    dr = [-1, 0, 0, 1]
    dc = [0, 1, -1, 0]
    total_sheep = 0
    total_wolf = 0
 
    for i in range(n*m):
        cur_r = i // m
        cur_c = i % m
        value = field[cur_r][cur_c]
 
        # 양과 늑대의 수를 센다.
        if value == 'v':
            total_wolf += 1
        elif value == 'o':
            total_sheep += 1
 
 
        # 방문하지 않은 늑대칸 발견
        if  not visited[cur_r][cur_c] and value == 'v':
            around_pos = []
            around_pos.append((cur_r,cur_c))
            visited[cur_r][cur_c] = True  # 방문 표시
 
            wolf = 0
            sheep = 0
            while around_pos:
                pos = around_pos.pop()
                r, c = pos
 
                v = field[r][c]
 
                if v == 'o': # 양
                    sheep += 1
                elif v == 'v': # 늑대
                    wolf += 1
                elif v == '#': # 울타리
                    continue
 
                # 상하좌우 체크
                for d in range(4):
                    temp_r = r + dr[d]
                    temp_c = c + dc[d]
 
                    # 범위 초과
                    if temp_r < 0 or temp_c < 0 or n <= temp_r or m <= temp_c:
                        continue
 
                    # 벽이거나 이미 방문한 곳
                    if field[temp_r][temp_c] == '#' or visited[temp_r][temp_c]:
                        continue
 
                    visited[temp_r][temp_c] = True  # 방문 표시
                    around_pos.append((temp_r, temp_c))
 
            # 양과 늑대 중 진 종족의 수를 전체 수에서 차감
            if wolf < sheep:
                total_wolf -= wolf
            else:
                total_sheep -= sheep
    return total_sheep, total_wolf
 
 
 
 
if __name__ == "__main__":
    n, m = map(int, input().strip().split())
    field = []
    for i in range(n):
        field.append(list(input().strip()))
 
    s, w = solve(n, m , field)
    print("{0} {1}".format(s, w))