[DFS/BFS/완전탐색] 1303번 - 전쟁 - 전투(BFS/DFS)

[백준] 1303번 - 전쟁 - 전투 

풀이 시간: 15~20분 이내

정석대로만 풀면 아주 쉽게 풀 수 있는 문제로 DFS, BFS 풀이가 모두 가능하다. DFS 풀이가 시간, 메모리 효율이 더 뛰어나다.

(풀이1) BFS

1) 문제 해결 아이디어

 

 

2) 소스코드

from collections import deque

# BFS
def bfs(x, y, color):
  cnt = 0  # 병사 수
  queue = deque()
  # 시작 지점 삽입, 방문 처리
  queue.append((x, y))
  graph[x][y] = 0

  while queue:
    x, y = queue.popleft()
    cnt += 1
    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] == color):
          queue.append((nx, ny))
          graph[nx][ny] = 0
  return cnt

n, m = map(int, input().split())  # 가로, 세로
# m * n (W:흰색 옷, B: 파란색 옷)
graph = [list(input()) for _ in range(m)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
    
white = 0
blue = 0
for i in range(m):
  for j in range(n):
    if(graph[i][j] == 'W'):
      white += (bfs(i, j, 'W'))**2
    elif(graph[i][j] == 'B'):
      blue += (bfs(i, j, 'B'))**2

print(white, blue)

 

(풀이2) DFS

1) 문제 해결 아이디어

Q. 14번 줄처럼 cnt에 dfs() 리턴 값을 대입해줘야하는 이유는? 

복습 필요

 

2) 소스코드

import sys
sys.setrecursionlimit(10**6)

# DFS
def dfs(x, y, cnt, color):
  # 현재 지점 방문 처리
  graph[x][y] = 0
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if(0 <= nx < m and 0 <= ny < n):
      # 방문한적이 없으면 현재 지점에서 dfs 호출
      if(graph[nx][ny] == color):
        cnt = dfs(nx, ny, cnt + 1, color)
  return cnt

n, m = map(int, input().split())  # 가로, 세로
# m * n (W:흰색 옷, B: 파란색 옷)
graph = [list(input()) for _ in range(m)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

white = 0
blue = 0
for i in range(m):
  for j in range(n):
    if(graph[i][j] == 'W'):
      white += (dfs(i, j, 1, 'W'))**2
    elif(graph[i][j] == 'B'):
      blue += (dfs(i, j, 1, 'B'))**2

print(white, blue)

[참고] https://jinho-study.tistory.com/907

백준 알고리즘 1303번 전쟁 - 전투(python)