[알고리즘][Python] 백준(BOJ) 1926 그림_파이썬

 

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

1926번: 그림

 

 

 

 

 

문제 풀기 전 공부할 것 : 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

 

 

 

 

 

 

풀이

<내용>

• bfs로 해결하기
• paint에 도화지 정보를 입력받는다.
• bfs 함수를 만들어 그림의 넓이를 구한다.
• 이미 확인했는지 아닌지를 위해 check 리스트를 만든다.
• paint 모든 곳을 돌며 그림인지 아닌지를 확인하고 그림이면 그림의 넓이를 구한다.

 

 

 

<코드>

import sys
input = sys.stdin.readline

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    w = 1
    que = [(x, y)]
    while que:
        x, y = que.pop()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if paint[nx][ny] == 1 and not check[nx][ny]:
                    w += 1
                    check[nx][ny] = 1
                    que.append((nx, ny))
    return w

cnt, wide = 0, 0
check = [[0]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if paint[i][j] == 1 and not check[i][j]:
            cnt += 1
            check[i][j] = 1
            wide = max(wide, bfs(i, j))
print(cnt)
print(wide)