[백준/알고리즘]#1303: 전쟁-전투 [파이썬(python)/그래프/DFS/BFS]

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

1303번: 전쟁 - 전투

그래프 DFS/BFS이론을 통해 푸는 문제다. 

BFS/DFS도 유형별로 푸는 방법이 달라지는데, 이 문제의 경우는 각각 기준점 별로 거리를 계산하는 문제다.

 

이와 비슷한 문제로는 

#2667: 단지번호 붙이기

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

 

#4963: 섬의 개수

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

가 있다.

 

 

처음엔 x, y좌표를 두고 좌우상하 방향을 잡는 로직 짜는게 어려웠는데, 

비슷한 여러 문제 풀면 비슷한애들끼리 금방 풀 수 있지 않을까?!!

 

파이썬 코드

#1303_전쟁-전투
import sys
from collections import deque
input = sys.stdin.readline

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

## W or B?
def bfs(x,y,col):
    q = deque()
    q.append((x,y))
    cnt=0
    
    while q:
        x,y = q.popleft()
        
        for i in range(4):#상하좌우 병사 탐색 
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < M and 0 <=ny < N:
                if color[nx][ny] == col and color[nx][ny]!=0:
                    q.append((nx,ny))
                    cnt+=1
                    color[nx][ny]=0
                    
    return (1 if cnt==0 else cnt)
    


N, M = map(int, input().split())

color = [list(input().strip()) for _ in range(M)]


w_cnt, b_cnt=0,0
for i in range(M):
    for j in range(N):
        if color[i][j]!=0:
            if color[i][j]=='W':
                w_cnt += bfs(i,j,color[i][j])**2
            elif color[i][j]=='B':
                b_cnt += bfs(i,j,color[i][j])**2
            
print(w_cnt, b_cnt)