[백준 BOJ_1743] 음식물 피하기 Python 풀이

출처: 백준 온라인 저지

문제

풀이

BFS로 구현해주었습니다.

방문할 때마다 visited를 1로 update 해주며, 상하좌우로 연결된 쓰레기의 개수를 cnt에 누적하여 세어주었습니다.

while loop이 끝날 때마다 result에 더 큰 값으로 저장해주었고 마지막에는 result를 출력해주었습니다.

코드

from collections import deque
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
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)]
result = 0
for _ in range(K):
  r, c = map(int, input().split())
  graph[r-1][c-1] = 1
for i in range(N):
  for j in range(M):
    if graph[i][j] and not visited[i][j]:
      queue = deque([(i, j)])
      visited[i][j] = 1
      cnt = 0
      while queue:
        y, x = queue.popleft()
        cnt += 1
        for k in range(4):
          ny, nx = y + dy[k], x + dx[k]
          if 0 <= ny < N and 0 <= nx < M and graph[ny][nx] and not visited[ny][nx]:
            visited[ny][nx] = 1
            queue.append((ny, nx))
      result = max(result, cnt)
print(result)