(Python) - BOJ(1303번) : 전투

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

1303번: 전쟁 - 전투

---

• 해설 : 

파란 옷을 입은 병사들과 하얀 옷을 입은 병사들이 뒤엉켜 싸우고 있다. 

N명의 병사들이 뭉쳐있을 경우 N^2의 힘을 낼 수 있다고 한다.

대각선에 있는 경우는 인접하지 않아 뭉쳐있다고 할 수 없다고 할 때,

 

파란 병사들와 하얀 병사들의 전투력 총합을 계산하는 문제이다.

 

 

 

---

• 풀이 :

BFS로 W 또는 B의 병사들을 만났을 때 탐색하고 인접한 병사들의 수를 리턴하여 이 값의 제곱값을 더해준다.

 

 

 

---

• 소스코드 : 

 

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
def bfs(start):
    queue = [start]
    cnt = 1
    ch = maps[start[0]][start[1]]
    maps[start[0]][start[1]] = 0
    while queue:
        x,y = queue[0]
        del queue[0]
        for k in range(4):
            ax = x + dx[k]
            ay = y + dy[k]
            if 0<=ax<M and 0<=ay<N:
                if ch == maps[ax][ay]:
                    queue.append([ax,ay])
                    maps[ax][ay] = 0
                    cnt +=1
    return cnt
 
if __name__ == "__main__":
    N,M = map(int,input().split())
    maps = []
    wC = 0
    bC = 0
    for _ in range(M):
        maps.append(list(input()))
    for i in range(M):
        for j in range(N):
            if maps[i][j] != 0:
                if maps[i][j] == "W":
                    cnt = bfs([i,j])
                    wC += cnt*cnt
                else:
                    cnt = bfs([i,j])
                    bC += cnt*cnt
 
    print(wC,bC)