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

문제

1303번: 전쟁 - 전투

- 전쟁은 어느덧 전면전이 시작되었다.

- 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다.

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

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

- N명이 뭉쳐있을 때는 N^2의 위력을 낼 수 있다.

- 과연 지금 난전의 상황에서는 누가 승리할 것인가?

- 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

- 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다.

- 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다.

- 모든 자리에는 병사가 한 명 있다. (B는 파랑, W는 흰색이다.)

알고리즘

- 우리 병사와 적군 병사의 위력을 측정하기 위해 각각의 dfs 탐색을 수행한다.

- N명이 뭉쳤있을 때 N^2의 위력을 낼 수 있기 때문에 병사의 수를 체크하고 제곱하여 위력을 측정한다. 

코드

import sys
sys.setrecursionlimit(10 ** 6)  # 재귀 허용 깊이를 수동으로 늘려주는 코드


# 우리 병사 dfs 탐색
def dfs_W(x, y):
    # 주어진 범위를 벗어나는 경우에 즉시 종료
    if x <= -1 or x >= m or y <= -1 or y >= n:
        return False

    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == "W":

        # 병사 수를 추가
        cnt_W.append(1)

        # 임의에 문자열로 해당 노드 방문 처리
        graph[x][y] = "E"

        # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
        dfs_W(x - 1, y)
        dfs_W(x, y - 1)
        dfs_W(x + 1, y)
        dfs_W(x, y + 1)

        return True
    return False


# 적군 병사 dfs 탐색
def dfs_B(x, y):
    # 주어진 범위를 벗어나는 경우에 즉시 종료
    if x <= -1 or x >= m or y <= -1 or y >= n:
        return False

    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == "B":

        # 병사 수를 추가
        cnt_B.append(1)

        # 임의에 문자열로 해당 노드 방문 처리
        graph[x][y] = "E"

        # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
        dfs_B(x - 1, y)
        dfs_B(x, y - 1)
        dfs_B(x + 1, y)
        dfs_B(x, y + 1)

        return True
    return False


n, m = map(int, sys.stdin.readline().split())

# 각 노드가 연결된 정보를 표현
graph = [list(map(str, input())) for _ in range(m)]

# 우리 병사 수와 위력
cnt_W = []
res_W = []

# 적군 병사 수와 위력
cnt_B = []
res_B = []

for i in range(m):
    for j in range(n):
        if dfs_W(i, j):
            # 우리 병사 위력을 계산하여 추가
            res_W.append(len(cnt_W) ** 2)
            cnt_W = []

        elif dfs_B(i, j):
            # 적군 병사 위력을 계산하여 추가
            res_B.append(len(cnt_B) ** 2)
            cnt_B = []

# 각 병사의 위력의 합을 출력
print(sum(res_W), sum(res_B))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법