728x90
반응형
기본적인 DFS & BFS 문제이다. 15092번 Sheba’s Amoebas와 같은 문제이다.
DFS 풀이
import sys
sys.setrecursionlimit(3000000)
def dfs(y, x):
graph[y][x] = '.'
for dy, dx in d:
Y, X = y+dy, x+dx
if (0 <= Y < m) and (0 <= X < n) and graph[Y][X] == '#':
dfs(Y, X)
m, n = map(int, input().split())
graph = [list(input()) for _ in range(m)]
d = [(-1, -1), (-1, 1), (1, -1), (1, 1), (-1, 0), (1, 0), (0, -1), (0, 1)]
cnt = 0
for i in range(m):
for j in range(n):
if graph[i][j] == '#':
dfs(i, j)
cnt += 1
print(cnt)
BFS 풀이
from collections import deque
def bfs(y, x):
q = deque()
q.append((y, x))
graph[y][x] = '.'
while q:
y, x = q.popleft()
for dy, dx in d:
Y, X = y+dy, x+dx
if (0 <= Y < m) and (0 <= X < n) and graph[Y][X] == '#':
q.append((Y, X))
graph[Y][X] = '.'
m, n = map(int, input().split())
graph = [list(input()) for _ in range(m)]
d = [(-1, -1), (-1, 1), (1, -1), (1, 1), (-1, 0), (1, 0), (0, -1), (0, 1)]
cnt = 0
for i in range(m):
for j in range(n):
if graph[i][j] == '#':
bfs(i, j)
cnt += 1
print(cnt)
728x90
반응형
'Agorithm > 백준 알고리즘' 카테고리의 다른 글
백준 알고리즘 14496번 그대, 그머가 되어(python) (0) | 2021.03.16 |
---|---|
백준 알고리즘 1325번 효율적인 해킹(python) (0) | 2021.03.16 |
백준 알고리즘 19621번 회의실 배정 2(python) (0) | 2021.03.16 |
백준 알고리즘 2210번 숫자판 점프(python) (0) | 2021.03.16 |
백준 알고리즘 11370번 Spawn of Ungoliant(python) (0) | 2021.03.14 |