[boj] 백준 14716 현수막 python 풀이

문제

 

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

14716번: 현수막

 

문제 풀이

가장 큰 섬을 찾는 bfs문제 응용

 

코드

import sys
input = sys.stdin.readline
import collections

M, N = map(int,input().split())
MAP = [list(map(int,input().split())) for _ in range(M)]
visited = [[0 for _ in range(N)] for _ in range(M)]

def bfs(MAP, sx, sy):
    q = collections.deque()
    q.append((sx,sy))

    while q:
        cx, cy = q.popleft()
        
        for tx, ty in [(-1,0),(0,1),(1,0),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)]:
            nx = cx + tx
            ny = cy + ty

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


res = 0
for i in range(M):
    for j in range(N):
        if MAP[i][j] == 1:
            bfs(MAP, i, j)
            res += 1
print(res)