[백준] 1303번 - 전쟁-전투 (파이썬)

 

백준 1303번 전쟁 - 전투 문제

 

 

 

이 문제는 전쟁터에서 뭉쳐있는 병사들을 찾아내어 그들의 전투력을 계산하는 문제로 예제 입력을 통해 알 수 있듯이 완전 탐색을 이용해 풀 수 있는 문제이다.

 

본인은 BFS를 사용하여 문제를 해결하였다.

 

 

" 💡 문제 해결 아이디어 "

 

문제는 말했다시피 BFS를 사용하여 해결하였다.

 

우선 bpower, wpower 변수를 0으로 미리 초기화시켜둔다.

 

그리고 입력받은 문자열(BWWWB.. 등)은 n개의 문자로 쪼개어 그래프에 한 줄씩 list단위로 저장하여 n X m 형태의 2차원 배열을 생성한다.

 

그래프 생성이 완료되면 그래프의 0,0부터 m-1,n-1 까지 탐색하면서 B또는 W를 찾는데 만약 해당 좌표의 값이 'B' 또는 'W'라면 bfs를 통해 뭉쳐있는 같은 팀 병사를 카운트하여 그 값을 리턴받는다.

( 카운트한 곳은 다시 카운트되지 않도록 'x' 문자로 변경해주었다. )

 

뭉쳐있는 병사 값을 리턴받으면 그 값의 제곱근을 구하고 탐색한 병사 뭉치가 'B'라면 bpower에 'W'라면 wpower에 더해준다.

 

이렇게하게 되면 병사들의 위력을 구해 누가 이길지 알아낼 수 있다!

 

 

 

코드

from collections import deque

def bfs(x,y,type):
    queue = deque([(x,y)])
    cnt = 1
    graph[x][y] = 'x'

    while queue:
        a,b = queue.popleft()
        for i in range(4):
            nx,ny = a+dx[i], b+dy[i]
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if graph[nx][ny] != type:
                continue
            if graph[nx][ny] == type:
                cnt += 1
                graph[nx][ny] = 'x'
                queue.append((nx,ny))
    return cnt

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

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

wpower, bpower = 0, 0

for i in range(n):
    for j in range(m):
        if graph[j][i] == 'B':
            bcnt = bfs(j,i,'B')
            bpower += (bcnt ** 2)
        elif graph[j][i] == 'W':
            wcnt = bfs(j,i,'W')
            wpower += (wcnt ** 2)

print(wpower, bpower)