[boj] 백준 1926 그림 python 풀이

전형적인 지도에서 가장 큰 섬을 찾는 문제. bfs 풀이함.

 

문제

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

1926번: 그림

 

코드

import sys
input = sys.stdin.readline
import collections

n,m = map(int,input().split())
MAP = [list(map(int,input().split())) for _ in range(n)]

move = {(-1,0),(0,1),(1,0),(0,-1)}

def bfs(x,y,MAP):
    q = collections.deque()
    q.append((x,y))
    MAP[x][y] = 2
    cnt = 1

    while q:
        x,y = q.popleft()

        for tx,ty in move:
            nx = tx + x
            ny = ty + y

            if 0<=nx<n and 0<=ny<m and MAP[nx][ny] == 1:
                q.append((nx,ny))
                MAP[nx][ny] = 2 #visited
                cnt += 1

    return cnt

pic_num, MAX = 0, 0
for i in range(n):
    for j in range(m):
        if MAP[i][j] == 1:
            pic_num += 1
            MAX = max(MAX,bfs(i,j,MAP))
            
print(pic_num)
print(MAX)