백준1303 - 전쟁 -전투 (BFS) python

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

문제는 가로 세로 크기인 n, m과 각 병사들의 옷 색상이 주어진다. 이때, 뭉쳐있는(상하좌우가 연결된) 병사들의 전투력은 n^2 라고 했을 때 각 팀의 전투력의 총합을 출력하면 된다.

 

문제 해결 방식

해당 문제에서는 DFS 알고리즘이나 BFS 알고리즘이나 큰 차이가 없을 것 같아 BFS 알고리즘으로 구현했다. 일반적인 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) :
  X,Y = map(int, data.pop(0).split())
  visited = [[False for _ in range(X)] for _ in range(Y)]
  
  def verify (x,y,tag) : 
    return 0 <= x < X and 0 <= y < Y and not visited[y][x] and data[y][x] == tag
  
  def BFS (x,y,tag) : 
    size = 1
    queue = deque()
    queue.append([x,y])
    visited[y][x] = True
    directions = [[0,-1],[0,1],[1,0],[-1,0]]
    
    while queue :
      [x,y] = queue.popleft()
      
      for dx,dy in directions :
        nx,ny = dx+x, dy+y
        if verify(nx,ny,tag) : 
          visited[ny][nx] = True
          queue.append([nx,ny])
          size += 1
          
    return size ** 2
  
  whiteTeam = blueTeam = 0
  
  for i in range(Y) :
    for j in range(X) :
      if not visited[i][j] : 
        if data[i][j] == 'W' : whiteTeam += BFS(j,i,data[i][j])
        else : blueTeam += BFS(j,i,data[i][j])
  
  print(whiteTeam, blueTeam)
          
solution(input_data)