[알고리즘] 백준 1303 전쟁 - 전투

문제

전쟁 - 전투

접근

1. 생각해야 할 점은, 0 1 로 구분되어서 1만 구하는것이 아니라 w b 모두 각자 구해야 하는 것이다.

2. 처음에는 w와 b에 대한 각각의 2차원 배열을 만들어서 접근을 하였다.

3. W,B에 대해서 count를 해서 배열에 넣어서 0, 1 인덱스로 하나씩 출력했다

 

하지만 좀 더 효율적으로 변경해 보았다 ( 위는 코드가 너무 중복된 문제가 있었다. )

1. 위와 비슷한 방식으로 접근을 했지만 w,b에 대한 각각의 배열을 만든것이 아니라 하나의 배열로 체크하였다

2. 또한 count를 해서 배열에 넣은것이 아니라 이중 for문을 돌면서 totalCount를 하여 바로 출력하는 방식으로 개선했다

풀이

# 전쟁 - 전투 -> Dfs
m, n = map(int, input().split())

board = []
for i in range(n):
    board.append(list(map(str, input())))

wCount = 0
wTotal = 0

bCount = 0
bTotal = 0


def dfs(x, y):
    global wCount

    if 0 <= x < n and 0 <= y < m and board[x][y] == 'W':
        board[x][y] = 'S'
        wCount += 1
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y-1)
        dfs(x, y+1)
        return True
    return False


def dfsS(x, y):
    global bCount

    if 0 <= x < n and 0 <= y < m and board[x][y] == 'B':
        board[x][y] = 'S'
        bCount += 1
        dfsS(x-1, y)
        dfsS(x+1, y)
        dfsS(x, y-1)
        dfsS(x, y+1)
        return True
    return False


for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            wTotal += wCount ** 2
            wCount = 0

for i in range(n):
    for j in range(m):
        if dfsS(i, j) == True:
            bTotal += bCount ** 2
            bCount = 0


print(wTotal, bTotal)