[백준] 1303 - 전쟁 - 전투

문제

백준 1303번 전쟁 - 전투

 

문제 링크 : https://www.acmicpc.net/problem/1303

 

 

문제 풀이

이 문제는 내 병사와 적국의 병사들이 각각 모여있을 때의 위력의 합을 구하는 것이다. 각 국가별 모여있는 병사의 수를 세는 것이므로, 연결된 노드 묶음을 찾는 방식으로 문제를 해결할 수 있다. 상하좌우에 위치한 연결된 노드를 탐색해나가는 전형적인 탐색 알고리즘 문제이며, DFS, BFS 모두로도 해결할 수 있지만 BFS로 풀이하였다.

방문 여부를 저장하는 visited라는 배열을 두어, 모든 노드를 방문하는 이중 반복문을 처리하며 visited가 False인 경우 bfs() 함수를 호출해 해당 노드가 속한 '묶음' 내 병사 인원 수를 파악한다. 'W'와 'B' 두 가지 키를 가진 딕셔너리 변수 dic에 해당 인원수의 제곱이 되는 수를 추가하는 식으로 각 병사의 위력을 갱신한다.

 

코드

import sys
from collections import deque

input = sys.stdin.readline

n,m=map(int, input().split(' '))
board=[list(map(str,input().rstrip())) for _ in range(m)]

d=[(0,1),(0,-1),(1,0),(-1,0)]
dic={'W':0,'B':0}
visited=[[False for _ in range(n)] for _ in range(m)]

def bfs(x,y,color):
  q=deque([(x,y)])
  cnt=1
  while q:
    i,j=q.popleft()
    for dx, dy in d:
      a=i+dx
      b=j+dy
      if 0<=a<m and 0<=b<n and not visited[a][b]:
        if board[a][b]==color:
          visited[a][b]=True
          q.append((a,b))
          cnt+=1

  return cnt

for i in range(m):
  for j in range(n):
    if not visited[i][j]:
      visited[i][j]=True
      val=bfs(i,j,board[i][j])
      dic[board[i][j]]+=val**2

print(dic['W'], dic['B'])