백준3184 - 양 (BFS) python

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

해당 문제는 울타리 '#'로 감싸진 영역 안에 있는 양 'o'과 늑대 'v'의 갯수를 헤아린 후, 더 많은 개체의 수만 누적으로 합산하여 출력하는 문제다.

문제 풀이 방식

울타리 안에 있는 영역 내 모든 개체의 수를 구하기 위해 BFS 알고리즘을 활용하여 접근했다. 울타리 내에 있는 각 개체의 합을 구한 뒤, 어떤 개체가 더 많은지 파악하고 이에 따라 누적해주는 방식으로 구현했다.

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()
from collections import deque


def solution (data) :
  Y,X = map(int, data.pop(0).split())
  matrix = data
  visited = [[False for _ in range(X)] for _ in range(Y)]

  wolves = 0 # 양
  sheep = 0 # 늑대
  
  def BFS (x,y) :
    nonlocal sheep, wolves
    o, v = 0, 0
    visited[y][x] = True
        
    queue = deque()
    queue.append([x,y])
    
    directions = [[0,-1],[0,1],[1,0],[-1,0]]
    while queue :
      x,y = queue.pop()
      if matrix[y][x] == 'v' : v += 1
      elif matrix[y][x] == 'o' : o += 1 
      
      for dx,dy in directions :
        nx,ny = dx+x, dy+y
        if 0 <= nx < X and 0 <= ny < Y and not visited[ny][nx] and matrix[ny][nx] != '#' :
          visited[ny][nx] = True
          queue.append([nx,ny])
    
    # 해당 울타리 안의 총 늑대와 양의 수를 구한 뒤, 누산
    if o > v : sheep += o
    else : wolves += v 
    
  for i in range(Y) :
    for j in range(X) : 
      if matrix[i][j] != '#' and not visited[i][j] :
        BFS(j,i)

  print(sheep, wolves)
  
solution(input_data)