백준 1303: 전쟁 - 전투

관련 링크 : https://www.acmicpc.net/problem/1303

백준 1303 : 전쟁 - 전투

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다.

그러나 당신의 병사들은 하얀 옷을 입고, 적국의 병사들은 파란옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다.

문제는, 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

N명이 뭉쳐있을 때는 N^2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

입력

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. (B는 파랑, W는 흰색이다.)

5 5
WBWWW
WWWWW
BBBBB
BBBWW
WWWWW

출력

첫 번째 줄에 당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력한다.

130 65

풀이

처음엔 어떤 식으로 해야 할지 바로 떠오르지 않았는데, 생각해 보니 각 전쟁터에서 BFS/DFS를 수행해 그래프에 속하는 모든 노드의 개수를 구하면 되는 문제였다. DFS가 더 익숙해서 DFS를 이용해 풀었다.

import sys

sys.setrecursionlimit(10000)

def getInput(): #입력 처리
    N, M = map(int, input().strip().split()) 
    zone = [input().strip() for _ in range(M)]
    return N, M, zone

def dfs(i, j, zone, team, N, M):
    global power, visited #
    for dx, dy in zip([1, -1, 0, 0], [0, 0, 1, -1]):
        if (
            0 <= i + dx < M
            and 0 <= j + dy < N #전쟁터 바깥
            and visited[i + dx][j + dy] == 0 #방문하지 않은 경우
            and zone[i + dx][j + dy] == team #같은 팀인 경우
        ):
            visited[i + dx][j + dy] = 1
            power += 1
            dfs(i + dx, j + dy, zone, team, N, M)

if __name__ == "__main__":
    N, M, zone = getInput()
    visited = [[0] * N for _ in range(M)]
    result = {"W": [], "B": []}
    for i in range(M):
        for j in range(N):
            power = 1 #시작 지점의 색을 기준으로 DFS
            if visited[i][j] == 0: 
                #이전 위치의 DFS에서 방문한 경우 들를 필요가 없음
                visited[i][j] = 1 
                dfs(i, j, zone, zone[i][j], N, M)
                result[zone[i][j]].append(power ** 2)
    print(sum(result["W"]), sum(result["B"]))