BOJ/백준-3187-python

문제

코드

# https://www.acmicpc.net/problem/3187
# boj, 3187: 양치기 꿍, python3
from collections import deque

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

# 탐색 함수 정의
def bfs(x: int, y: int):
    # 양과 늑대의 수를 담은 변수 전역변수화
    global k, v
    # queue 초기화
    queue = deque()
    queue.append([x, y])
    # 현재 위치 방문 처리
    visited[x][y] = True
    # 울타리 영역 내 양과 늑대의 수를 담는 변수
    k_num, v_num = 0, 0

    # 현재 울타리 영역이 양이면 영역 내 양의 수 증감
    if fence[x][y] == 'k':
        k_num += 1
    # 현재 울타리 영역이 늑대이면 영역 내 늑대 수 증감
    if fence[x][y] == 'v':
        v_num += 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 fence[nx][ny] != '#':
                visited[nx][ny] = True  # 방문처리
                queue.append([nx, ny])
                if fence[nx][ny] == 'k':
                    k_num += 1
                if fence[nx][ny] == 'v':
                    v_num += 1
    # 같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많을 경우 늑대가 전부 잡아먹힌다. 물론 그 외의 경우는 양이 전부 잡아먹히겠지만 말이다.
    if k_num and v_num:
        if k_num > v_num:
            v -= v_num
        else:
            k -= k_num


if __name__ == '__main__':
    # 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다.
    r, c = map(int, input().split())
    # 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다.
    # 빈 공간을 '.'(점)으로 나타내고 울타리를 '#', 늑대를 'v', 양을 'k'
    k, v = 0, 0  # 양과 늑대의 수를 담는 변수
    fence = []

    for x in range(r):
        tmp = list(input())
        for y in range(c):
            if tmp[y] == 'k':  # 현재 반복문 요소가 k이면 양의 수 증감
                k += 1
            if tmp[y] == 'v':  # 현재 반복문 요소가 v이면 늑대 수 증감
                v += 1
        fence.append(tmp)

    # 방문처리를 담는 List
    visited = [[False] * c for _ in range(r)]

    # 탐색 시작
    for x in range(r):
        for y in range(c):
            if fence[x][y] == 'k' or fence[x][y] == 'v':
                if not visited[x][y]:
                    visited[x][y] = True
                    bfs(x, y)

    # 살아남게 되는 양과 늑대의 수를 각각 순서대로 출력한다.
    print(k, v)

결과

출처 & 깃허브

BOJ
Github