[BOJ] 백준 1303. 전쟁 - 전투

🥈 전쟁 - 전투, 실버 1

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

💡 아이디어

전형적인 탐색문제.

N명이 뭉쳐있을땐 N제곱 만큼의 위력을 낸다고 한다.

W의 위력

상하좌우 기준으로 상단에 덩어리 9 → 81

하단의 덩어리 7 → 49

130

B의 위력

상단 1

하단에 8 → 64

65

⚠️ 탐색 알고리즘을 이용해서 W(B)의 갯수를 찾고, 각각의 리스트에 저장하여 제곱한뒤 더하여 return 한다

📝 풀이

# 백준 전쟁 - 전투
from collections import deque
# 가로 세로
n, m = map(int, input().split())
war = []
for i in range(m):
    war.append(list(map(str, input().rstrip())))
    

def bfs_w(wy, wx):
    w = 0
    q.append((wy,wx))
    visited[wy][wx] = True
    while q:
        y, x = q.popleft()
        if war[y][x] == 'W':
            w += 1   
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < m and war[ny][nx] == 'W' and not visited[ny][nx]:
                    visited[ny][nx] = True
                    q.append((ny,nx))          
    w_l.append(w)

def bfs_b(by,bx):
    b = 0
    q.append((by,bx))
    visited[by][bx] = True
    while q:
        y, x = q.popleft()
        if war[y][x] == 'B':
            b += 1   
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < m and war[ny][nx] == 'B' and not visited[ny][nx]:
                    visited[ny][nx] = True
                    q.append((ny,nx))          
    b_l.append(b)    

w_l = []
b_l = []

q = deque()

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

visited= [[False] * n for _ in range(m)]
for i in range(m):
    for j in range(n):
        if not visited[i][j] and war[i][j] == 'W':
            bfs_w(i,j)

visited = [[False] * n for _ in range(m)]
for i in range(m):
    for j in range(n):
        if not visited[i][j] and war[i][j] == 'B':
            bfs_b(i,j) 
            
w_result = 0
for i in range(len(w_l)):
    w_result += w_l[i] * w_l[i] 

b_result = 0
for i in range(len(b_l)):
    b_result += b_l[i] * b_l[i] 

print(w_result, b_result)

🇸🇲 느낀점

방문처리가 정말 중요하다!

코드가 길어지다보니 깜빡해서 답이 의도와 다르게 나왔다,,

그리고 각각의 개수를 갱신해주고, while문이 끝나면 리스트에 append 해주는 것을 잊지말자!!