알고리즘/백준 문제풀이

[boj] 백준 1926 그림 python 풀이

감자156 2023. 4. 30. 11:25
반응형

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

 

문제

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

 

1926번: 그림

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로

www.acmicpc.net

 

코드

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)
반응형