[boj] 백준 1303 전쟁 - 전투 python 풀이

감자156 2023. 4. 30. 13:02

bfs로 풀이함

문제

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

1303번: 전쟁 - 전투

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는

www.acmicpc.net

코드

import sys
input = sys.stdin.readline
import collections

N, M = map(int,input().split())
MAP = [list(input()) for _ in range(M)]

move = {(-1,0),(0,1),(1,0),(0,-1)}

def bfs(x,y,MAP,color):
    q = collections.deque()
    q.append((x,y))
    MAP[x][y] = 'Z'
    cnt = 1

    while q:
        x,y = q.popleft()

        for tx,ty in move:
            nx = tx + x
            ny = ty + y

            if 0<=nx<M and 0<=ny<N and MAP[nx][ny] != 'Z' and MAP[nx][ny] == color:
                q.append((nx,ny))
                MAP[nx][ny] = 'Z' #visited
                cnt += 1

    return cnt

Blue, White = 0, 0
for i in range(M):
    for j in range(N):
        if MAP[i][j] == 'W':
            White += bfs(i,j,MAP,'W')**2
        elif MAP[i][j] == 'B':
            Blue += bfs(i,j,MAP,'B')**2
        
print(White, Blue)