1303 - 전쟁 - 전투

info

• 문제 보기: 1303 - 전쟁 - 전투
• 소요 시간: 22분 42초
• 풀이 언어: python
• 체감 난이도: 1️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

DFS

풀이 코드

info

• 메모리: 31132 KB
• 시간: 36 ms

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

data, visited = [], []
ours, theirs = 0, 0
n, m = 0, 0

def dfs(y, x, team):
    global visited
    
    if data[y][x] != team:
        return 0
    
    visited[y][x] = True
    
    cnt = 1 # self
    if y+1 < m and data[y+1][x] == team and not visited[y+1][x]: # bottom
        cnt += dfs(y+1, x, team)
    if x+1 < n and data[y][x+1] == team and not visited[y][x+1]: # right
        cnt += dfs(y, x+1, team)
    if y > 0 and data[y-1][x] == team and not visited[y-1][x]: # top
        cnt += dfs(y-1, x, team)
    if x > 0 and data[y][x-1] == team and not visited[y][x-1]: # left
        cnt += dfs(y, x-1, team)
    
    return cnt

def solution():
    global n, m, data, visited, ours, theirs
    n, m = map(int, input().split())
    for _ in range(m):
        visited.append([False] * (n))
        data.append(list(input().rstrip()))
        
    for i in range(m):
        for j in range(n):
            if not visited[i][j]:
                if data[i][j] == 'W':
                    ours += dfs(i, j, 'W') ** 2
                elif data[i][j] == 'B':
                    theirs += dfs(i, j, 'B') ** 2
                
    
    print(ours, theirs)


if __name__ == '__main__':
    solution()

• 한 번 방문하여 카운팅한 좌표는 재방문할 일이 없으므로 visited를 해제하지 않는다.

풀이 해설

4방향 진행인 이유?

• 다음의 그림은 4방향이 모두 필요한 case의 한 예를 나타낸다.

  

메모

• 쉬워서 다시 안풀어도 될 듯