[BOJ] 1303. 전쟁-전투

www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

풀이

• queue를 사용한 DFS문제.
• visited 2차원 리스트를 만들어 방문했는지 여부를 저장
• 첫 시작점 방문 -> DFS로 갈수 있는 모든 점 방문
  • 방문하면서 visited를 업데이트
• 방문 끝나면 다시 순차적으로 다음 위치 탐색(visited에 이미 방문했으면 건너뜀)

def solution(M, N, m):
    """
    M : 가로
    N : 세로
    m : 병사 배치 매트릭스
    """
    w_score = 0
    b_score = 0
    visited = [[False for _ in range(M)] for _ in range(N)]

    queue = []
    queue.append([0, 0])
    for i in range(N):
        for j in range(M):
            if visited[i][j] == False:
                queue = [[i, j]]
                # 해당 지점이 B인지, W인지를 저장.
                blue_or_white = 'B' if m[i][j] == 'B' else 'W'
                cnt = 0
                while queue:
                    x, y = queue.pop()
                    cnt += 1
                    visited[x][y] = True
                    # 1. 다음 방문할 위치 index가 주어진 matrix안에 들어와야함
                    # 2. matrix에서 다음 방문할 위치가 처음 방문이어야 함(visited == False)
                    # 3. matrix에서 다음 방문할 위치가 처음 위치의 병사와 동일해야 함.
                    if x+1 < N and visited[x+1][y] == False and m[x+1][y] == blue_or_white:
                        queue.append([x+1, y])
                        visited[x+1][y] = True

                    if y+1 < M and visited[x][y+1] == False and m[x][y+1] == blue_or_white:
                        queue.append([x, y+1])
                        visited[x][y+1] = True

                    if x-1 >= 0 and visited[x-1][y] == False and m[x-1][y] == blue_or_white:
                        queue.append([x-1, y])
                        visited[x-1][y] = True

                    if y-1 >= 0 and visited[x][y-1] == False and m[x][y-1] == blue_or_white:
                        queue.append([x, y-1])
                        visited[x][y-1] = True

                if blue_or_white == 'B':
                    b_score += cnt**2
                else:
                    w_score += cnt **2

    return w_score, b_score

import sys
M, N = map(int, sys.stdin.readline().split(' '))

m = []
for _ in range(N):
    lst = [i for i  in sys.stdin.readline().strip()]
    m.append(lst)

rs = solution(M, N, m)
print(rs[0], rs[1])