[백준 1303번] 전쟁 - 전투 -python

문제 링크

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

1303번: 전쟁 - 전투

 

풀이 

- bfs 문제

- 계속 런타임 에러 떠서 이유를 찾느라 한참 걸렸는데 가로 크기가 N 이고 세로 크기가 M 인 이유 때문이었다. 

- 병사 색깔을 함께 넘겨주어 뭉쳐있는 병사들의 수를 구해 리턴한다. 

- 개수를 센 병사의 위치는 "#"로 표시하여 준다. 

- 병사 수의 제곱을 더해준다. 

from collections import deque 

nx = [ 1, -1, 0, 0 ]
ny = [ 0, 0, 1, -1 ]

def bfs(color,i,j):
  # 병사 수 
  count = 1 
  
  q= deque()
  q.append((i,j))
  # 방문 표시 
  maps[i][j] = "#"
  
  while q :
    x, y = q.popleft()

    for i in range(4):
      dx = x + nx[i]
      dy = y + ny[i]
    
      if 0 <= dx < m and 0 <= dy < n and maps[dx][dy] == color:
        count += 1
        maps[dx][dy] = "#"
        q.append((dx,dy))

  return count

n, m = map(int,input().split())

maps = []

for _ in range(m):
  maps.append(list(map(str,input())))

b_num = 0
w_num = 0 

for i in range(m):
  for j in range(n):
  
    if maps[i][j] == 'B':
      tmp = bfs('B',i,j)
      b_num += tmp * tmp 
      
    elif maps[i][j] == 'W':
      tmp = bfs('W',i,j)
      w_num += tmp * tmp 

print(w_num,b_num)