[python 파이썬] 백준 1303번 : 전쟁 - 전투

BFS/DFS 좋은 문제 추천

https://won-percent.tistory.com/34?category=1145094

문제

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

풀이

dfs - 재귀      bfs - 큐

를 이용해서 푸는 것이 일반적이라고 저번 첫 문제 풀때 이야기했다.

이번건 사실 dfs로 푸는줄 알았는데 bfs 였다.

주변에 아군인지 적군인지 알아야하기에 bfs 로 부는것 같다.

저번에 사용했던 *list 를 사용해서 변수를 받아보려했는데 다른 더 편한 방법이 있었다.

strip() 를 사용하면 list로 했을때 받아와지는 '/n' 를 없애줬고 편하게 입력값을 원하는 방식으로 받았다.

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
field = [list(input().strip()) for i in range(m)]
check = [[0]*n for _ in range(m)]
q = deque()
w_power, b_power = 0, 0


def sol():
 q.append((i, j))
 check[i][j] = 1
 cnt = 1
 while q:
 x, y = q.popleft()
 for dx, dy in (1, 0), (-1, 0), (0, 1), (0, -1):
 nx, ny = x+dx, y+dy
 if 0 <= nx < n and 0 <= ny < n:
 if field[nx][ny] == field[x][y] and check[nx][ny] == 0:
 check[nx][ny] = 1
 q.append((nx, ny))
 cnt += 1
 return cnt


for i in range(m):
 for j in range(n):
 if check[i][j] == 0:
 ans = sol()
 if field[i][j] == 'W':
 w_power += ans ** 2
 else:
 b_power += ans ** 2

print(w_power, b_power)