728x90
전쟁 - 전투
문제
전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다.
그러나 당신의 병사들은 하얀 옷을 입고, 적국의 병사들은 파란옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다.
문제는, 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.
N명이 뭉쳐있을 때는 N^2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.
입력
첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. (B는 파랑, W는 흰색이다.)
출력
첫 번째 줄에 당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력한다.
2개의 색을 보고 연결 되어있는 것을 파악하면 되니깐
브루트포스하게 모든 구역을 확인하면서 bfs로 몇개가 연결되어있는지 확인하는 방식을 사용하고자 하였다.
그래서 연결되어있는 수 만큼 카운트하여 bfs가 끝난 뒤 제곱을 하여 더하는 방식을 사용하였다.
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
num_list = [list(input()) for _ in range(M)]
dirs = [(-1,0),(0,1),(1,0),(0,-1)]
# 위치, 색깔
def bfs(x,y,C):
global cnt_W, cnt_B
q = [(x,y,C)]
# 다른 아무 문자로 visit 역할을 대신
num_list[x][y] = "A"
# 카운트는 현재부터 시작하기 때문에 1로 시작
cnt = 1
# bfs 시작
while q:
i,j,C = q.pop(0)
# 탐색
for dir in dirs:
ni = i + dir[0]
nj = j + dir[1]
# 범위안에서 같은 색이면
if 0<= ni < M and 0 <= nj < N and num_list[ni][nj] == C:
q.append((ni,nj,C))
num_list[ni][nj] = "A"
# 연결된 병사 증가
cnt += 1
# 그 색에 카운트를 제곱해서 증가
if C == "W":
cnt_W += cnt ** 2
else:
cnt_B += cnt ** 2
cnt_W = 0
cnt_B = 0
# 모든 곳을 탐색
for i in range(M):
for j in range(N):
# 그 색에 맞게 bfs
if num_list[i][j] == "W":
bfs(i,j,"W")
elif num_list[i][j] == "B":
bfs(i,j,"B")
print(cnt_W,cnt_B)
'@@@ 알고리즘 > 백준 스터디' 카테고리의 다른 글
20444(색종이와 가위) - 해결 (0) | 2021.10.13 |
---|---|
2668(숫자고르기) - 해결 (0) | 2021.10.13 |
11559(Puyo Puyo) - 해결 (0) | 2021.10.10 |
17392(우울한 방학) - 해결 (0) | 2021.10.10 |
16953(A → B) - 해결 (0) | 2021.10.09 |