python] 백준 1743 음식물 피하기

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

 

 

문제 해결

일반적인 bfs문제;

 

CODE

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

def bfs(x,y):
    que = deque()
    dxs = [-1, 1, 0, 0]
    dys = [0, 0, -1, 1]
    que.append((x,y))
    visited[x][y] = 1
    result = 1
    while que:
        a, b = que.popleft()
        for dx, dy in zip(dxs, dys):
            na = a + dx; nb = b + dy
            if 0<na<=n and 0<nb<=m and visited[na][nb] == 0 and graph[na][nb] == 1:
                visited[na][nb] = 1
                result += 1
                que.append((na,nb))
    return result

if __name__ == "__main__":
    n, m, k = map(int, input().split())
    graph = [[0 for _ in range(m+1)] for _ in range(n+1)]
    visited = [[0 for _ in range(m+1)] for _ in range(n+1)]
    for _ in range(k):
        r, c = map(int, input().split())
        graph[r][c] = 1
    ans = 0
    for i in range(1,n+1):
        for j in range(1,m+1):
            if graph[i][j] == 1 and visited[i][j] == 0:
                res = bfs(i,j)
                ans = max(ans, res)
    print(ans)