백준 1303 : 전투 파이썬 문제 풀이(bfs 알고리즘 사용)

 

백준 1303 번 전투 문제입니다. 

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

1303번: 전쟁 - 전투

 

 

아군은 W, 적군은 B이고 n명이 뭉쳐있을 때 n^2의 위력을 나타내니 bfs 탐색을 사용하면 되겠습니다. 

 

 

입력의 첫째 줄은 전쟁터의 가로 길이, 세로 길이이며 전쟁터의 모습이 출력됩니다.

5 5
WBWWW
WWWWW
BBBBB
BBBWW
WWWWW

출력입니다

130 65

 

 

저는 입력 받는 것 때문에 인덱스 에러를 겪어서 다른 예제도 적어봅니다. 

#입력
4 6
BBBB
BWBW
WWBW
WWWW
WBBW
BWWW

#출력
196 54

 

 

저의 처음 생각은 W를 탐색하는 bfs와 B를 탐색하는 bfs를 분리해야한다고 생각했습니다. 

그래서 이렇게 분리해서 코드를 짰습니다. 

그런데 생각해보니 "B" 또는 "W"만 달라서 묶어서 다시 짜보았습니다.

from collections import deque

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

war = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
#아군힘, 적군힘 저장
power = [0 for _ in range(2)]

for i in range(m):
    war.append(list(input()))


def bfsW(x, y):
    queue = deque()
    queue.append((x, y))
    war[x][y] = -1
    cnt = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if war[nx][ny] == "W":
                war[nx][ny] = -1
                queue.append((nx, ny))
                cnt += 1
    return cnt * cnt

def bfsB(x, y):
    queue = deque()
    queue.append((x, y))
    war[x][y] = -1
    cnt = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if war[nx][ny] == "B":
                war[nx][ny] = -1
                queue.append((nx, ny))
                cnt += 1
    return cnt * cnt



for i in range(m):
    for j in range(n):
        if war[i][j] == "W":
            power[0] += bfsW(i, j)
        if war[i][j] == "B":
            power[1] += bfsB(i, j)
#" ".join(power) 하면 type에러가 생김
print(" ".join(map(str, power)))

 

 

최종 코드입니다. 

from collections import deque

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

war = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
power = [0 for _ in range(2)]

for i in range(m):
    war.append(list(input()))


def bfs(x, y, a):
    queue = deque()
    queue.append((x, y))
    war[x][y] = -1
    cnt = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if war[nx][ny] == a:
                war[nx][ny] = -1
                queue.append((nx, ny))
                cnt += 1
    return cnt * cnt


for i in range(m):
    for j in range(n):
        if war[i][j] == "W":
            power[0] += bfs(i, j, "W")
        if war[i][j] == "B":
            power[1] += bfs(i, j, "B")

print(" ".join(map(str, power)))