Coding Test/스터디
[DFS&BFS] 백준_1303_전쟁전투
AssunI_Dev
2023. 11. 15. 13:12
https://www.acmicpc.net/problem/1303
1303번: 전쟁 - 전투
첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는
www.acmicpc.net
문제
입출력
풀이&사용알고리즘: BFS
- 그래프 직접 만들어주기
- w,b의 그래프 따로 만들어주기
- w, b 에 해당하는 bfs 개별적으로 이루어지도록 하고 접수 넣어주기
전체코드
from collections import deque
def bfs(x, y , maps):
queue = deque()
queue.append((x, y))
checked_list = list()
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
scale = 0
while queue:
x, y = queue.popleft()
for j in range(4):
nx = x + dx[j]
ny = y + dy[j]
if nx < 0 or ny < 0 or nx >= len(maps) or ny >= len(maps[0]):
continue
if maps[nx][ny] == 0:
continue
if maps[nx][ny] == 1:
scale += 1
maps[nx][ny] = 0
queue.append((nx, ny))
return scale
def main():
N, M = map(int, input().split())
graph = []
for i in range(N):
graph.append(list(map(str, input().split())))
print(graph)
maps_w = [[0] * M for _ in range(N)]
maps_b = [[0] * M for _ in range(N)]
for i in range(0, len(graph)):
for j in range(0, len(graph[i])):
if graph[i][j] == 'W':
maps_w[i][j] = 1
elif graph[i][j] == 'B':
maps_b[i][j] = 1
print(maps_w, maps_b)
score_w = 0
score_b = 0
for i in range(len(graph)):
for j in range(0, len(graph)):
if graph[i][j] == 'W':
result_w = bfs(i, j, maps_w)
score_w += (result_w * result_w)
for i in range(len(graph)):
for j in range(0, len(graph)):
if graph[i][j] == 'B':
result_b = bfs(i, j, maps_b)
score_b+= (result_b * result_b)
return score_w, score_b
print(main())