[백준1303] / 전쟁 - 전투 - DFS

 

백준1303

 

푼 날짜 : 2024.09.011

푼 문제 : [1303] / 전쟁 - 전투

사용한 언어 : python

 

 

푼 방법 :

DFS로 접근하였다. 

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

 

 

같은 병사가 몇 명이 뭉쳐있는지를 계산하고 그 인원의 제곱을 구한다.

우리 병사와 적국 병사의 위력의 총합을 출력한다.

 

범위 계산과 추가적으로 현재의 target과 일치하면 지속해서 DFS를 실행하고 아니라면 제곱값을 총합에 더하여 다음 과정을 진행하도록 구현했다.

 

 

코드 :

import sys

N, M = map(int, sys.stdin.readline().split())
graph_ = []
visited = [[0 for _ in range(N)] for _ in range(M)]
for _ in range(M):
    row = list(sys.stdin.readline().rstrip())
    graph_.append(row)

W_sum, B_sum = 0, 0 # 부분합 계산
W_score, B_score = 0, 0 # 전체 위력의 합 계산

px = [1, -1, 0, 0]
py = [0, 0, 1, -1]
def DFS(v, t):
    global W_sum, B_sum
    visited[v[0]][v[1]] = 1
    
    for i in range(4):
        ny, nx = v[0]+py[i], v[1]+px[i]
        if 0<=ny<M and 0<=nx<N:
            if not visited[ny][nx] and graph_[ny][nx] == t:
                if t == 'W': W_sum += 1
                else: B_sum += 1
                DFS((ny, nx), t)

           
for i in range(M):
    for j in range(N):
        if not visited[i][j]:
            t = graph_[i][j]
            if t == 'W': W_sum += 1
            else: B_sum += 1
            DFS((i, j), t) 
            if t == 'W': 
                W_score += W_sum**2
                W_sum = 0
            else: 
                B_score += B_sum**2
                B_sum = 0
            
print(W_score, B_score)

 

 

전형적인 DFS + 방문하는 값 개수의 제곱을 합하는 계산으로 생각보다 쉬운 문제였다.

오늘도 1일 1알고리즘 성공~ \ \ \٩( ′ㅂ`)و ̑̑/ / /