백준 1303 전쟁- 전투

백준 1303 전쟁- 전투

 

문제

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

1303번: 전쟁 - 전투

분류

그래프

pass(복습필요)

하지만, 시간 지난뒤 다시 풀어봐야 할것같다. 

dfs, bfs 문제는 자주 안보면 풀이법을 자꾸 까먹는것같다.

 

풀이

2023.08.11 - [알고리즘] - softeer, 장애물 인식 프로그램

softeer, 장애물 인식 프로그램

이 문제에서 탐색할 수 있는 조건에 같은 team인지 여부가 추가됨!

 

 

전체 코드

import sys
input = sys.stdin.readline

C, R = map(int, input().split())
# C, R = 5, 5

board = []
# board = [['W', 'B', 'W', 'W', 'W'], ['W', 'W', 'W', 'W', 'W'], ['B', 'B', 'B', 'B', 'B'], ['B', 'B', 'B', 'W', 'W'], ['W', 'W', 'W', 'W', 'W']]
for _ in range(R):
    board.append(list(input()))

# 북동남서
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

def dfs(r, c, team):
    global cnt

    board[r][c] = 'V' # 방문표시
    cnt += 1

    # 갈 수 있는지 탐색
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        
        if 0 <= nr < R and 0 <= nc < C and board[nr][nc] == team:
            dfs(nr, nc, board[nr][nc])

w_score = 0
b_score = 0
for r in range(R):
    for c in range(C):
        # 방문한 적 없을 경우
        if board[r][c] != 'V':
            cnt = 0 # 초기화
            team = board[r][c]
            dfs(r, c, team)
            if team == 'W':
                w_score += cnt ** 2
            elif team == 'B':
                b_score += cnt ** 2

print(w_score, b_score)