백준 1743번 : 음식물 피하기

일반적인 DFS/BFS 문제다.
인접해 있는 음식물을 하나의 음식물로 보고 가장 큰 음식물의 크기를 구하는 문제다.

그럼 왜 글을 썼냐?

요즘 그래프 탐색 문제를 풀면서 메모리초과가 자주 났다. 처음에는 이해가 안됐다. 탐색문제 풀면서 할당하는 리스트는 써봤자 graph와 visited에 추가로 queue나 stack을 사용하는 게 다다. 근데 이정도로 초과라고?

# 틀린 코드

처음엔 이중 for문을 사용해 i,j를 넣었다. 그래서 이거때문에 메모리초과가 발생하는줄 알고 쓰레기 위치를 따로 저장해 하나씩 뽑아써봤는데도 해결이 안됐다. 그럼 뭐가 문제야?????

import sys
from collections import deque
input = sys.stdin.readline
N, M, K = map(int, input().split())
graph = [[0 for _ in range(M)] for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]
trash = []
for i in range(K):
  r, c = map(int, input().split())
  graph[r-1][c-1] = 1
  trash.append([r, c])


def bfs(x, y):
  queue = deque([[x, y]])
  visited[x][y] = 1
  count = 1
  mx = [-1, 1, 0, 0]
  my = [0, 0, -1, 1]

  while queue:
    x, y = queue.popleft()
    for i in range(4):
      dx = x + mx[i]
      dy = y + my[i]

      if dx < 0 or dy < 0 or dx >= N or dy >= M:
        continue
      
      if graph[dx][dy] == 1:
        visited[dx][dy] = 1
        graph[x][y] = 0
        count += 1
        queue.append([dx, dy])
    
  return count


max_count = 0
while trash:
  i, j = trash.pop()
  i, j = i-1, j-1
  if visited[i][j] == 0 and graph[i][j] == 1:
    max_count = max(max_count, bfs(i, j))
print(max_count)

# 정답 코드

차이를 알겠는가? 위 코드와 아래 코드의 차이점은 방문여부를 조건문에 포함시키느냐 안시키느냐에 차이다. 근데 정확히는 방문여부 체크가 문제가 아니다.
방문여부 체크를 같이 안하면서 queue에 들어가는 데이터양이 많아지게 되고 메모리초과가 발생하는 것이다.
사실 글쓰면서 위 코드를 수정했더니 정답처리가 됐다.
근데 이전에도 메모리초과 떴었는데 DFS를 안쓰고 BFS로 풀었더니 정답처리가 됐었다. 아마 재귀를 돌면서 데이터가 중복되게 들어간 것 같다. 같은 오류로 틀린 사람이 많아서 위안이 됐다(?)

결론적으로 하고싶은 말은 메모리초과라는 오류가 발생했을 때 queue나 stack에 중복되게 들어가는 데이터가 없는지 확인해보는 것이 좋다.

맞게 코드를 짰다고 생각했을 때도 특정한 상황에서 중복된 데이터가 여러개 들어가 초과되는 경우가 있으니 조심해야 한다.

import sys
from collections import deque
input = sys.stdin.readline
N, M, K = map(int, input().split())
graph = [[0]*M for _ in range(N)]
visited = [[0]*M for _ in range(N)]
trash = []
for i in range(K):
  r, c = map(int, input().split())
  graph[r-1][c-1] = 1
  trash.append([r, c])


def bfs(x, y):
  queue = deque([[x, y]])
  visited[x][y] = 1
  count = 1
  mx = [-1, 1, 0, 0]
  my = [0, 0, -1, 1]

  while queue:
    x, y = queue.popleft()
    for i in range(4):
      dx = x + mx[i]
      dy = y + my[i]

      if dx < 0 or dy < 0 or dx >= N or dy >= M:
        continue

      if graph[dx][dy] == 1 and visited[dx][dy] == 0:
        visited[dx][dy] = 1
        count += 1
        queue.append([dx, dy])
    
  return count


max_count = 0
while trash:
  i, j = trash.pop()
  i, j = i-1, j-1
  if graph[i][j] == 1 and visited[i][j] == 0:
    max_count = max(max_count, bfs(i, j))
print(max_count)