문제 1303 전쟁 - 전투

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

Solution

import sys
input = sys.stdin.readline
from collections import deque
m, n = map(int, input().split())

graph = []
for _ in range(n):
    graph.append(input())

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

def bfs(x, y):
    visited[x][y] = 1
    cnt = 1
    queue = deque()
    queue.append((x, y))
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            if graph[x][y] == graph[nx][ny] and visited[nx][ny] == 0:
                visited[nx][ny] = 1
                cnt += 1
                queue.append((nx, ny))
    return cnt ** 2


result = 0
result2 = 0

visited = [[0] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'W' and visited[i][j] == 0:
            result += bfs(i, j)
        if graph[i][j] == 'B' and visited[i][j] == 0:
            result2 += bfs(i, j)

print(result, result2)

배운점

이 문제가 기본 bfs/dfs문제심화된 점

• 리스트 안이 0 or 1에서 문자(W, B)로 바뀐것
• 기존엔 1을 0으로 바꿔가는 식으로 방문처리 해 줬지만 따로 처리해야함
• W인 경우, B인경우 두 가지경우를 모두 구해야 한다는 것.

풀이는 생각보다 간단하다.
조건만 몇개 추가하고 변경해 주면 된다.

시작점을 따로 두지 않고 (0, 0)부터 반복하며 돌게 하고

• 'W'와 같고 방문하지 않았다면 bfs
• 'B'와 같고 방문하지 않았다면 bfs
• 상하좌우를 돌며 같은 값이고 방문하지 않았다면 방문처리하고 cnt += 1

생각보다 간단하게 풀려서 기분이 좋다.