[백준-1303] 전쟁 - 전투

문제

링크

풀이

import sys
from collections import deque
input = sys.stdin.readline

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

war = []
wteam, bteam = 0, 0
visited = [[0]*n for _ in range(m)]

for _ in range(m) :
    war.append(input())
    
queue = deque()
for i in range(m) :
    for j in range(n) :
        if visited[i][j] == 1:
            continue
        queue.append((i, j))
        power = 1
        visited[i][j] = 1
        while queue :
            q = queue.popleft()
            for a, b in [[-1, 0], [0, 1], [1, 0], [0, -1]] :
                da = a + q[0]
                db = b + q[1]
                if 0 <= da <= m-1 and 0 <= db <= n-1 and war[da][db] == war[i][j]:
                    if visited[da][db] == 0 :
                        queue.append((da, db))
                        visited[da][db] = 1
                        power += 1
        if war[i][j] == 'W' :
            wteam += power**2
        else :
            bteam += power**2

print(wteam, bteam)

이 문제는 bfs를 이용해서 풀었다.

1. 방문여부 확인
   1-1. 방문했을 경우, continue
   1-2. 방문하지 않았을 경우, 큐에 좌표를 넣고 방문 처라
2. 해당 좌표 상, 하, 좌, 우가 같은 색상인지 확인.
   2-1. 같은 색상일 경우, 큐에 넣고 방문처리, power += 1
   2-2. 다른 색상일 경우, coninue
3. queue가 비었을 경우 각각 색의 전체 합에 더하기
4. 모든 좌표를 순회했을 경우 각각 출력하기

bfs로 풀면 되는 간단한 문제였다.
한동안 알고리즘 문제를 많이 못풀어서 bfs/dfs 감을 다 잃었다..ㅠㅠ
감을 다시 줍줍 하기 위해 쉬운 문제부터 열른 풀어봐야겠다.