[DFS/BFS/완전탐색] 1926번 - 그림(BFS)

[백준] 1926번 - 그림

풀이 시간: 10분 이내

아주 쉽게 해결할 수 있었던 문제이다. 그림의 개수와 그 중 가장 넓은 그림의 넓이를 출력하는 문제로 BFS, DFS로 모두 풀이가 가능한 유형이다. 하지만 다른 사람들의 DFS 풀이를 찾아봐도 시간초과나 메모리초과 문제가 다수가 발생했다. 아래 글에 따르면 DFS에서 방향벡터를 이용해 for문을 돌리지 않으면 메모리 초과가 뜨지 않았지만 이런 문제의 경우 그냥 BFS로 풀이하는 것이 좋을 듯 하다.

 

DFS는 재귀 방식으로 수행되기 때문에 호출할 때마다 스택에 쌓여 메모리를 많이 차지하게 되고 

BFS는 큐에 쌓이는 객체의 크기가 크지 않다면 훨씬 적은 비용이 발생하므로 메모리 측면에서 유리할 수 있다. 오늘의 교훈! 상황에 따라 DFS, BFS 풀이를 해야한다!!!!!!!!

(풀이1) BFS(성공 코드)

1) 문제 해결 아이디어

 

2) 소스코드

from collections import deque

# BFS
def bfs(x, y):
  size = 0  # 그림 넓이
  queue = deque()
  # 시작 지점 삽입, 방문 처리
  queue.append((x, y))
  graph[x][y] = 2

  while queue:
    x, y = queue.popleft()
    size += 1
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if(0 <= nx < n and 0 <= ny < m):
        # 방문하지 않은 곳이면 삽입, 방문 처리
        if(graph[nx][ny] == 1):
          queue.append((nx, ny))
          graph[nx][ny] = 2
  return size

n, m = map(int, input().split())  # 세로, 가로
# 0: 색칠X, 1: 색칠O
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

cnt = 0       # 그림 개수
max_size = 0  # 가장 큰 그림의 넓이
for i in range(n):
  for j in range(m):
    if(graph[i][j] == 1):
      max_size = max(max_size, bfs(i, j))      
      cnt += 1

print(cnt)
print(max_size)

(풀이2) DFS (메모리 초과 실패 코드)

1) 문제 해결 아이디어

보통의 경우, DFS로 풀면 메모리 초과가 뜬다. 아래 글을 참고하면 DFS를 사용함에도 성공할 수 있는 코드가 있으니 참고하면 좋을 듯 하다.

 

2) 소스코드

import sys
sys.setrecursionlimit(10**6)

# DFS
def dfs(x, y):
  global size
  # 현재 지점 방문처리
  graph[x][y] = 2
  size += 1

  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if(0 <= nx < n and 0 <= ny < m):
      # 방문하지 않은 곳이면 현재 좌표에서 dfs 호출
      if(graph[nx][ny] == 1):
        dfs(nx, ny)

n, m = map(int, input().split())  # 세로, 가로
# 0: 색칠X, 1: 색칠O
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

cnt = 0       # 그림 개수
max_size = 0  # 가장 큰 그림의 넓이
size = 0
for i in range(n):
  for j in range(m):
    if(graph[i][j] == 1):
      size = 0
      dfs(i, j)
      max_size = max(max_size, size)      
      cnt += 1


print(cnt)
print(max_size)

[참고] https://velog.io/@a87380/1926%EB%B2%88-%EA%B7%B8%EB%A6%BC-%ED%8C%8C%EC%9D%B4%EC%8D%AC

1926번 그림 파이썬