[BOJ / Python] 1303 - 전쟁 - 전투

문제 링크

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

1303번: 전쟁 - 전투

---

풀이

• 파이썬의 deque 모듈을 이용해 BFS를 구현하였다.
• BFS를 하기 전 memo 변수에 W팀의 탐색을 진행하는지, B팀의 탐색을 진행하는지 기록하였다. (line 16)
  • 탐색 조건으로 memo 변수에 저장된 팀에 속한 병사인지 체크한다. (line 24)
• num 변수는 모여있는 병사들의 수를 센다. (line 15)
  • 탐색 조건을 만족하면 num 수를 1씩 올린다. (line 27)
• 한 위치에 대한 BFS 탐색이 끝나면 어떤 팀의 탐색을 진행했는지 memo를 통해 체크한 후, 해당 팀의 병사 수에 2의 제곱을 해준다. (line 28~31)

---

코드

from collections import deque

n, m = map(int, input().split())
arr = [list(input()) for _ in range(m)]

dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
visit = [[0]*n for _ in range(m)]
w_power = 0
b_power = 0

for i in range(m):
    for j in range(n):
        num = 0
        if visit[i][j] == 0:
            num+=1
            memo = arr[i][j]
            visit[i][j] = 1
            q = deque()
            q.append([i,j])
            while q:
                x, y = q.popleft()
                for k in range(4):
                    nx, ny = x+dx[k], y+dy[k]
                    if 0 <= nx < m and 0 <= ny <n and visit[nx][ny] == 0 and arr[nx][ny] == memo:
                        visit[nx][ny] = 1
                        q.append([nx,ny])
                        num+=1
            if memo == "W":
                w_power += num**2
            else:
                b_power += num**2
print(w_power, b_power)