[BOJ / 백준] 1303번 전쟁 - 전투 파이썬 (Python) 문제 풀이

문제

 

문제 링크 : https://www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

 

 

 

 

CODE

from collections import deque
import sys

input = sys.stdin.readline
dir = [[0, -1], [0, 1], [1, 0], [-1, 0]]


def solve(x, y, ground, check):
    q = deque([[x, y]])
    check[y][x] = True
    cnt = 0

    while q:
        x, y = q.popleft()
        cnt += 1

        for d in dir:
            dx, dy = x + d[0], y + d[1]
            if 0 <= dx < n and 0 <= dy < m and ground[y][x] == ground[dy][dx] and check[dy][dx] == False:
                q.append([dx, dy])
                check[dy][dx] = True
    return cnt


if __name__ == '__main__':
    n, m = map(int, input().split())
    ground = []
    w_res = b_res = 0
    for _ in range(m):
        temp = input().rstrip()
        ground.append(list(temp))

    check = [[False] * n for _ in range(m)]

    for y in range(m):
        for x in range(n):
            if not check[y][x]:
                temp = solve(x, y, ground, check)
                if ground[y][x] == 'W':
                    w_res += temp ** 2
                else:
                    b_res += temp ** 2

    print(w_res, b_res)

 

 

 

 

 

풀이

💡 idea

- BFS

- 방문하지 않은 노드에 대해 인접한 노드를 count하며 방문처리

- 아군 / 적군에 따라 공격력을 따로 저장한다

 

💡 implementation

- 이동방향

dir = [[0, -1], [0, 1], [1, 0], [-1, 0]]

 

- 방문할 노드가 배열 범위 안에 있는지, 같은 군에 속했는지, 방문했던 노드인지 판단하는 if문

if 0 <= dx < n and 0 <= dy < m and ground[y][x] == ground[dy][dx] and check[dy][dx] == False:

 

- 아군 / 적군에 따라 결과 따로 저장

if ground[y][x] == 'W':
    w_res += temp ** 2
else:
    b_res += temp ** 2

 

 

 

 

 

결과