[백준] 1926 그림 BFS (DFS는 참고만 하기 메모리 초과)

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))