728x90
[백준] 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
728x90
'[Python]알고리즘 > 백준' 카테고리의 다른 글
[DFS/BFS/완전탐색] 1926번 - 그림(BFS) (0) | 2022.04.06 |
---|---|
[DFS/BFS/완전탐색] 17086번 - 아기 상어2(BFS) (0) | 2022.04.06 |
[DFS/BFS/완전탐색] ▲ 13913번 - 숨바꼭질 4(BFS) (0) | 2022.04.05 |
[DFS/BFS/완전탐색] ★ 13549번 - 숨바꼭질 3(BFS) (0) | 2022.04.05 |
[DFS/BFS/완전탐색] ★ 12851번 - 숨바꼭질 2(BFS) (2) | 2022.04.05 |