BFS로 문제 풀기
# 백준 1926 그림
# BFS
from collections import deque
def bfs(x, y):
queue = deque()
cnt = 1
queue.append((x, y))
visited[x][y] = True
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx<0 or ny<0 or nx>=n or ny>=m or visited[nx][ny]:
continue
if graph[nx][ny] == 1:
cnt += 1
visited[nx][ny] = True
queue.append((nx, ny))
return cnt
n, m = map(int, input().split())
graph = []
for _ in range(n):
graph.append(list(map(int, input().split())))
visited = [[False] *m for _ in range(n)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
count, MAX = 0, 0
lst=[]
for x in range(n):
for y in range(m):
if graph[x][y] == 1 and not visited[x][y]:
count += 1
MAX = max(MAX, bfs(x, y))
print(count)
print(MAX)
주의할 점
visited[x][y] = True
visited[nx][ny] = True
둘 다 해줘야 오류가 안남
후자를 안해줄 시 중복이 많아짐
count 변수는 1인 영역이 몇개인지에 관한 변수
MAX와 함수 bfs의 cnt 변수는 각 영역의 넓이 변수
DFS 문제 풀 시 메모리 초과 떴음
# 메모리 초과로 실패
# 총 분야 개수 구하기 + 각 분야 넓이 구하기 참고하기
# 백준 1926 그림
import sys
sys.setrecursionlimit(10000000)
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
visited = [[False] * m for _ in range(n)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def dfs(x, y):
global cnt
cnt += 1
visited[x][y] = True
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx<0 or ny<0 or nx>=n or ny>= m or visited[nx][ny]:
continue
if graph[nx][ny] == 1:
dfs(nx, ny)
count = 0
lst = []
for x in range(n):
for y in range(m):
if graph[x][y] == 1 and not visited[x][y]:
cnt = 0
dfs(x, y)
lst.append(cnt)
if len(lst)==0:
print(len(lst))
print(0)
else:
print(len(lst))
print(max(lst))
[파이썬] 백준 2839 설탕 배달 (0) | 2022.03.08 |
---|---|
[백준] 1003 피보나치 함수 (보텀업) (0) | 2022.03.08 |
[파이썬] 백준 1920: 수 찾기 (이진 탐색) (0) | 2021.08.28 |
[파이썬] 백준 2920: 음계 (구현) (0) | 2021.08.28 |
[파이썬] 백준 1946: 신입 사원 (그리디 알고리즘, 정렬) (0) | 2021.08.28 |