[백준] 1303 전투 - 파이썬

문제

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

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

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

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

입력

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

출력

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

 

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

1303번: 전쟁 - 전투

 

 

---

풀이

전형적인 bfs/dfs 문제였다.

지난 번 파이프 옮기기 문제에서 배운대로.. 완전탐색이어서 bfs/dfs 중 dfs를 사용해봤다.

 

1. 완전탐색을 진행하며 'c' (checked라는 뜻)가 아닌 'B'나 'W'가 나오면, dfs를 시행한다.

   1-1. 문제 조건대로 상하좌우에 같은 병사가 있으면 cnt에 1을 더하고 그 자리에서 dfs 시행

   1-2. 주변에 같은 병사가 없으면 cnt를 제곱해서 더함

2. 완전탐색이 끝날때까지 반복

import sys
input = sys.stdin.readline

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

#가장자리 처리 조건을 간소화하기 위해 보드 감싸기 #'c'는 checked
board = [['c']*(n+2)] + [['c'] + list(input())[:-1] +['c'] for _ in range(m)] + [['c']*(n+2)]

cnt = 0
force = {'B': 0, 'W': 0} #정답을 저장할 set
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)] #상하좌우 방향
def dfs(r, c, type): #dfs
    global cnt
    cnt += 1
    for d in dir:
        if board[r+d[0]][c+d[1]] == type:  #상하좌우에 같은 병사가 있음
            board[r+d[0]][c+d[1]] = 'c'
            dfs(r+d[0], c+d[1], type)

for r in range(1, m+1):
    for c in range(1, n+1):
        if board[r][c] != 'c': #확인하지 않은 병사가 있음
            cnt = 0
            type = board[r][c]
            board[r][c] = 'c'
            dfs(r, c, type)
            force[type] += cnt**2

print(str(force['W']) + " " + str(force['B']))

금방 풀었다. 뿌듯