[백준] 1303번 전쟁 - 전투

문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

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

입력

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

출력

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

예제 입력 1

5 5
WBWWW
WWWWW
BBBBB
BBBWW
WWWWW

예제 출력 1 복사

130 65

내 코드

from collections import deque

DIR = [(0, -1), (0, 1), (-1, 0), (1, 0)]  # 상하좌우

def bfs(matrix, start_x, start_y, color):
    q = deque([(start_x, start_y)])
    matrix[start_y][start_x] = 'V'  # 방문처리
    near_counts = 1

    while q:
        x, y = q.popleft()
        for dx, dy in DIR:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < M and matrix[ny][nx] == color:
                matrix[ny][nx] = 'V'  # 방문처리
                near_counts += 1  # 근접 병사 합 증가
                q.append((nx, ny))

    return near_counts * near_counts

N, M = map(int, input().split())
matrix = [list(input()) for _ in range(M)]
W_power = 0
B_power = 0

for j in range(M):
    for i in range(N):
        if matrix[j][i] != 'V':
            if matrix[j][i] == 'W':
                W_power += bfs(matrix, i, j, 'W')
            elif matrix[j][i] == 'B':
                B_power += bfs(matrix, i, j, 'B')

print(W_power, B_power)

chatGPT

개선 코드

from collections import deque

# 상하좌우 방향 벡터
DIRECTIONS = [(0, -1), (0, 1), (-1, 0), (1, 0)]

def bfs(matrix, start_x, start_y, color):
    queue = deque([(start_x, start_y)])
    matrix[start_y][start_x] = 'V'  # 방문 처리
    size = 1  # 현재 그룹 크기

    while queue:
        x, y = queue.popleft()
        for dx, dy in DIRECTIONS:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < M and matrix[ny][nx] == color:
                matrix[ny][nx] = 'V'  # 방문 처리
                size += 1
                queue.append((nx, ny))

    return size ** 2  # 병사 그룹의 위력 계산

# 입력 처리
N, M = map(int, input().split())
matrix = [list(input().strip()) for _ in range(M)]  # 공백 제거 처리
white_power = 0
blue_power = 0

# BFS를 통해 각 병사 그룹의 위력을 계산
for y in range(M):
    for x in range(N):
        if matrix[y][x] != 'V':  # 방문하지 않은 경우
            if matrix[y][x] == 'W':
                white_power += bfs(matrix, x, y, 'W')
            elif matrix[y][x] == 'B':
                blue_power += bfs(matrix, x, y, 'B')

# 출력
print(white_power, blue_power)

---

개선 사항

1. 가독성 개선: 변수명 및 방향 벡터 명확화
   • ~~DIR → DIRECTIONS: 이름을 명확히 변경하여 방향 벡터의 용도를 직관적으로 이해할 수 있습니다.~~
   • ~~near_counts → size: 그룹 크기를 표현하는 변수명을 간결하고 의미 있게 변경했습니다.~~
2. 리스트 입력 처리 방식 수정
   • ~~strip()을 추가하여 입력 문자열에서 불필요한 공백을 제거했습니다. 이는 입력 값에 공백이 포함될 가능성을 방지합니다.~~
3. 불필요한 반복 제거
   • BFS 함수에서 matrix[start_y][start_x] = 'V' 방문 처리를 함수 진입 시 바로 처리하도록 변경했습니다.
   • 중복 방문 확인을 위한 조건문을 줄이고, 코드 흐름을 단순화했습니다.
4. 그룹 크기 계산 방식 유지
   • 기존 코드에서 near_counts를 증가시키며 그룹 크기를 계산하는 방식은 효율적이었기에 유지했습니다. 단, * 연산자 사용으로 위력 계산을 명확히 표현했습니다.
5. 상수 처리 방식 통일
   • 방향 벡터와 관련된 상수를 코드 맨 위로 정리하여, 상수값을 한눈에 확인할 수 있도록 개선했습니다.
6. 출력 변수명 통일
   • ~~W_power, B_power → white_power, blue_power: 가독성과 일관성을 위해 변수명을 명확히 변경했습니다.~~

부가 질문

내 생각

1. 제곱 계산 방법: size ** 2