[Python] 백준 1303 전쟁 - 전투 - BFS/DFS

백준 홈페이지 문제와 개인적인 풀이를 작성한 글입니다.

 

백준문제 - 1303 : 전쟁 - 전투

1303번: 전쟁 - 전투

 

---

문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

 

N명이 뭉쳐있을 때는 N^2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

 

입력 

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. B는 파란색, W는 흰색이다. 당신의 병사와 적국의 병사는 한 명 이상 존재한다.

 

출력

첫 번째 줄에 당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력한다.

 

예제 입력 1	예제 출력 1
5 5 WBWWW WWWWW BBBBB BBBWW WWWWW	130 65

 

1 차 코드 - (오답) DFS

반례를 찾지 못했습니다. (댓글로 남겨주세요..)

import sys

input = sys.stdin.readline

# 번째 수 입력받기
n, m = map(int, input().split())

graph = []

result = [0, 0]

for i in range(m):
  graph.append(list(map(str, input())))

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

def DFS(x, y, z):
  if x <= -1 or x >= n or y <= -1 or y >= m:
    return False
  # K 라는 무의미 한 값을 넣는다.

  if z == 'W' and graph[x][y] == 'W':
    
    graph[x][y] = '-'
    global count_W 
    count_W += 1
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      DFS(nx, ny, 'W')
    return True
  if z == 'B' and graph[x][y] == 'B':
    graph[x][y] = '-'
    global count_B
    count_B += 1
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      DFS(nx, ny, 'B')
    return True
  return False

for i in range(m):
  for j in range(n):
    if DFS(i, j, 'W') == True:
      result[0] += count_W **2
    if DFS(i, j, 'B') == True:
      result[1] += count_B **2
    count_W = 0
    count_B = 0
        
print(result[0], result[1])

 

2차 코드 - 다른 분 코드 참고 정답 BFS

from collections import deque
import sys

input = sys.stdin.readline
n, m = map(int, input().split())

graph = []
for i in range(m):
  graph.append(list(input()))

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

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

count_W = 0
count_B = 0

def bfs(x, y, z):
  count = 1
  q = deque()
  q.append((x, y))
  visited[x][y] = True

  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0 <= nx < m and 0 <= ny < n :
        if graph[nx][ny] == z and visited[nx][ny] == False:
          visited[nx][ny] = True
          q.append((nx, ny))
          count += 1
  return count

for i in range(m):
  for j in range(n):
    if graph[i][j] == 'W' and visited[i][j] == False:
      count_W += bfs(i, j, 'W') ** 2
    elif graph[i][j] == 'B' and visited[i][j] == False:
      count_B += bfs(i, j, 'B') ** 2

print(count_W, count_B)