[boj] 백준 1743 음식물 피하기 python 풀이

문제

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

1743번: 음식물 피하기

 

문제 풀이

가장 큰 섬을 찾는 bfs 문제

 

코드

import sys
input = sys.stdin.readline
import collections

N, M, K = map(int, input().split())
MAP = [[0 for _ in range(M)] for _ in range(N)]
for i in range(K):
    r, c = map(int,input().split())
    MAP[r-1][c-1] = 1 # 음식물

def bfs(x,y,MAP):
    move = {(-1,0),(0,1),(1,0),(0,-1)}
    q = collections.deque()
    q.append((x,y))
    MAP[x][y] = -1 # visited

    cnt = 1
    while q:
        cx, cy = q.popleft()

        for tx, ty in move:
            nx = tx + cx
            ny = ty + cy

            if 0<=nx<N and 0<=ny<M and MAP[nx][ny] == 1:
                q.append((nx, ny))
                MAP[nx][ny] = -1
                cnt += 1

    return cnt

MAX = 0
for i in range(N):
    for j in range(M):
        if MAP[i][j] == 1:
            island_area = bfs(i,j,MAP)
            MAX = max(island_area, MAX)

print(MAX)