1303 전쟁

💡문제 분석 요약

• 구역별로 병사들이 몇명 있는지 구한다. 해당 구역 내에 병사들의 power는 병사들 수의 제곱이다.
• white, blue 각각의 power를 구한다.

💡알고리즘 설계

• DFS, BFS 둘 다 가능하다.
• 상하좌우 체크와, 병사들 수 체크만 잘 하면 된다. 병사들 총 수는 DFS 실행횟수와 같다.

💡코드

import sys
sys.setrecursionlimit(10**6)

# 가로, 세로 "길이"가 n, m임. 즉 행:m , 열:n
n, m = map(int, input().split())  # 가로가 열 개수, 세로가 행 개수라는 것을 헷갈리면 안됨 !!!!!!!!!!!!!!!!!!!!!!!!!!
war = [list(input()) for _ in range(m)] # 여기서도 range(n)이 아니라 m임.

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# white, blue 병사들 총 수
white = 0
blue = 0

"""
1. 방문한 곳 재방문 안하기 위한 처리
2. 상하좌우 접근 가능한지 체크 & 가야하는 곳인지 체크 (ex. 값이 1이거나, 여기서처럼 아군이거나 등)
3. 해당 위치로 이동, 새로운 DFS 매개변수 설정 (ex. 병사 수 1명 늘리기, color 넘겨주기 등)
"""
def find_soldiers(x, y, soldier, color):
    war[x][y] = 0 # 해당 위치는 이제 탐색 안하기 위해 0으로 바꿈

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0 <= nx < m and 0 <= ny < n) and (war[nx][ny] == color): # 상하좌우가 접근범위 내에 있고 and 아군이라면(같은 색이라면)
            soldier = find_soldiers(nx, ny, soldier + 1, color) # 해당 위치로 이동 & 병사 수 1명 늘려줌
    return soldier # dfs 탐색 끝나면 지금껏 탐색한 병사들의 총 수를 리턴


for i in range(m):
    for j in range(n):
        if (war[i][j] == 'W'):
            white += (find_soldiers(i, j, 1, 'W')) ** 2 # 리턴값이 한 영역의 병사들 총 수니까 바로 제곱해서 합쳐줌
        elif (war[i][j] == 'B'):
            blue += (find_soldiers(i, j, 1, 'B')) ** 2


print(white, blue)

💡시간복잡도

• 모든 곳을 for문으로 방문하므로 O(m*n)

💡 틀린 이유

• 가로n, 세로m으로 썼는데 사실 이게 행열로 따지면 가로가 5개 있다는 게 "열이 5개"라는 소리고, 세로가 7개라는 것은 "행이 7개"라는 소리다. 즉, 가로 길이 열, 세로 길이가 행이라는 것을 알아야한다. (매우 매우 중요, 이거 인지 못해서 계속 틀림) -> 그래서 for문 돌릴 때도 m이 먼저 돌아가는 것.

💡 틀린 부분 수정 or 다른 풀이

• 가로 n을 y좌표와 비교하고, 세로 m은 x좌표와 비교한다.

💡 느낀점 or 기억할정보

• 행과 열 파악 잘하기.