문제 1743 음식물 피하기

https://www.acmicpc.net/problem/1743

Solution

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

n, m, k = map(int, input().split())
graph = [[0]*(m+1) for _ in range(n+1)]

for _ in range(k):
    r, c = map(int, input().split())
    graph[r][c] = 1

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    graph[x][y] = 0
    cnt = 1
    queue = deque()
    queue.append((x, y))
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 1 or ny < 1 or nx > n or ny > m:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                cnt += 1
                queue.append((nx, ny))
    return cnt
    

result = []
for i in range(1, n+1):
    for j in range(1, m+1):
        if graph[i][j] == 1:
            result.append(bfs(i, j))

print(max(result))

배운점

기존의 bfs/dfs문제들과 다른점은 크게 없었지만, 범위를 잘 봐야된다.
N, M, K의 범위를 제대로 알아야 문제의 조건을 정확히 설정할 수 있다.
그래프는 (0, 0)부터 시작인데 문제의 범위는 N >= 1, M >= 1
K >= N*M으로 기존문제들이랑 범위가 살짝 달랐다. 문제를 주의해서 보자!!