[백준] 1743번 음식물 피하기

💡문제접근

• BFS 탐색 알고리즘을 이용해서 문제를 해결할 수 있었다. 자주 접했던 유형의 문제라 조금은 익숙한 것 같다.

💡코드(메모리 : 34192KB, 시간 : 72ms)

from collections import deque
import sys
input = sys.stdin.readline

def BFS(x, y):
    cnt = 0
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True
    while queue:
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and school[nx][ny] == 1 and not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx,ny))
                cnt += 1
    return cnt + 1

N, M, K = map(int, input().strip().split())
school = [[0] * M for _ in range(N)]
visited = [[False] * M for _ in range(N)]
for _ in range(K):
    a, b = map(int, input().strip().split())
    school[a-1][b-1] = 1

answer = 0
for a in range(N):
    for b in range(M):
        if school[a][b] == 1 and not visited[a][b]:
            answer = max(BFS(a, b), answer)
print(answer)

💡소요시간 : 28m