BOJ/백준-3184-python

문제

코드

# https://www.acmicpc.net/problem/3184
# boj, 3184: 양, python3
from collections import deque

# 이동방향 정의
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

def bfs(x: int, y: int):
    # 양과 늑대의 수를 전역변수화
    global o, v
    # 울타리 영역 내 양의 수, 울타리 영역 내 늑대의 수
    area_o, area_v = 0, 0
    # queue 초기화
    queue = deque()
    queue.append([x, y])

    if yard[x][y] == 'o':  # 현재 그래프 순회 요소가 양이면 영역 내 양의 수 증감
        area_o += 1
    if yard[x][y] == 'v':  # 현재 그래프 순회 요소가 늑대이면 영역 내 늑대 수 증감
        area_v += 1

    # 큐가 빌 때까지 반복
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 상, 하, 좌, 우 위치 체크
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 주어진 범위를 벗어나는지 확인
            if 0 <= nx < r and 0 <= ny < c and visited[nx][ny] == False and yard[nx][ny] != '#':
                if yard[nx][ny] == 'o':
                    area_o += 1
                if yard[nx][ny] == 'v':
                    area_v += 1
                visited[nx][ny] = True  # 방문처리
                queue.append([nx, ny])
    # 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아낸다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.
    if area_o and area_v:
        if area_o > area_v:
            v -= area_v
        else:
            o -= area_o

if __name__ == '__main__':
    # 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다.
    r, c = map(int, input().split())
    # 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다.
    o, v = 0, 0
    # 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다.
    yard = []

    for x in range(r):
        data = list(input())
        for j in range(c):
            if data[j] == 'o':
                o += 1
            if data[j] == 'v':
                v += 1
        yard.append(data)

    # 그래프(마당) 방문처리를 담는 list
    visited = [[False] * c for _ in range(r)]

    # 탐색 시작
    for x in range(r):
        for y in range(c):
            if yard[x][y] == '0' or yard[x][y] == 'v':
                # 현재 위치가 방문하지 않았으면 방문처리 후 탐색 시작
                if not visited[x][y]:
                    visited[x][y] = True
                    bfs(x, y)

    # 하나의 줄에 아침까지 살아있는 양과 늑대의 수를 의미하는 두 정수를 출력한다.
    print(o, v)

결과

출처 & 깃허브

boj
github