[백준] S1. boj3187 양치기 꿍 / 분류: bfs

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

import sys
from collections import deque

input = sys.stdin.readline
R, C = map(int, input().split())

map = []
for i in range(R):
    map.append(list(input().strip()))
visited = [[0] * C for i in range(R)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

wolf = 0
sheep = 0
queue = deque()

def bfs(i, j):
    queue.append((i, j))
    visited[i][j] = 1
    wolf_count, sheep_count = 0, 0
    while queue:
        x, y = queue.popleft()
        if map[x][y] == 'v': #늑대면
            wolf_count += 1
        elif map[x][y] == 'k': #양이면
            sheep_count += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < R and 0 <= ny < C:
                if map[nx][ny] != '#' and not visited[nx][ny]:
                    visited[nx][ny] = 1
                    queue.append((nx, ny))
    if sheep_count > wolf_count:
        wolf_count = 0
    else:
        sheep_count = 0
    return (wolf_count, sheep_count)

for r in range(R):
    for c in range(C):
        if map[r][c] != "#" and not visited[r][c]: #양을 만나면 queue에 추가. 근데 이렇게만 하면 늑대의 마리 수를 모두 구할 수 없을 수도.
            wolf_count, sheep_count = bfs(r, c)
            wolf += wolf_count
            sheep += sheep_count

print(sheep, wolf)

 

• 전역에 R, C와 map을 입력받고, 방문처리를 하는 배열 visited 생성
• bfs 함수
  • 파라미터로 i, j를 받아 배열의 인덱스를 받아 queue에 추가하고 방문처리 후 울타리 내의 늑대와 양 수를 저장하는 wolf_count와 sheep_count를 0으로 초기화.
  • queue에 원소가 있으면 while loop를 돎
    • queue에서 배열의 인덱스 x, y를 저장받고, 늑대거나 양인 경우를 센다.
    • dx와 dy 배열을 이용해서 배열 이동하고, 울타리가 아니면서 방문하지 않았으면 방문 처리 후에 queue에 append
  • 결과 리턴
    • 울타리 안에 양이 늑대보다 더 많으면 늑대는 모두 잡아먹힘 -> wolf_count = 0
    • 이외의 경우에는 양이 모두 잡아먹힘 -> sheep_count = 0