[Python] BOJ 3187 - 양치기 꿍(koze)

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

3187번: 양치기 꿍

1. 영역을 m에 입력받고, 반복문을 돌며 현재 칸이 '#'이 아니라면 bfs함수를 실행한다.

 

   * bfs함수: 양의 수를 저장할 변수 sheep과 늑대 수를 저장할 변수 wolf를 선언해준다.

       현재 칸이 v이면 wolf += 1, 현재 칸이 k이면 sheep += 1

       q에 넣고 bfs를 돌리는데, 다음칸이 맵 밖을 벗어나지 않고 '#'이 아니라면

       (nx, ny)를 방문처리해주고, (nx, ny)가 v이면 wolf 1증가, k이면 sheep을 1증가시킨다.

 

2. 최종적으로 큐의 좌표를 모두 방문한 뒤, sheep > wolf이면 양이 더 많으므로 answer[0]에

       sheep을 증가시켜주고, sheep <= wolf이면 늑대가 양을 다 잡아먹으므로

       answer[1]에 wolf를 증가시킨다.

 

3. 모든 칸을 방문 한 뒤, answer의 값을 출력한다.

 

import sys
from collections import deque
input = sys.stdin.readline
R, C = map(int,input().split())
m = []
for _ in range(R):
    m.append(list(input().rstrip()))
answer = [0, 0]         # sheep, wolf
q = deque()
visited = [[False] * C for _ in range(R)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

def bfs(i, j):
    sheep, wolf = 0, 0
    if m[i][j] == 'v':
        wolf = 1
    if m[i][j] == 'k':
        sheep = 1
    q.append((i, j))
    visited[i][j] = True
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < R and 0 <= ny < C and not visited[nx][ny] and m[nx][ny] != '#':
                visited[nx][ny] = True
                if m[nx][ny] == 'v':
                    wolf += 1
                elif m[nx][ny] == 'k':
                    sheep += 1
                q.append((nx, ny))
    
    if sheep > wolf:
        answer[0] += sheep
    else:
        answer[1] += wolf


for i in range(R):
    for j in range(C):
        if m[i][j] != '#' and not visited[i][j]:
            bfs(i, j)

print(*answer)

(solved.ac 티어: 실버 2)