[탐색/BFS] 백준 1926 그림 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1926번: 그림

 

 

 

2. 문제 풀이

 1로 이어진 그림의 개수와, 그림의 최대 크기를 구하는 BFS 문제입니다.

 

2022.02.23 - [Algorithm] - [탐색/BFS] 백준 1012 유기농 배추 - Python

[탐색/BFS] 백준 1012 유기농 배추 - Python

 

 

3. 코드

from collections import deque
import sys
input = sys.stdin.readline

# 입력
n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))


# bfs
direction = [(1,0), (0,1), (-1,0), (0,-1)]

def bfs(x, y):
    graph[x][y] = 0
    queue = deque([(x, y)]) # 시작지점
    size = 1 # 집 크기
    while queue:
        x, y = queue.popleft()
        for dx, dy in direction:
            nx, ny = x+dx, y+dy
            # 범위 내 방문하지 않은 곳이면 탐색
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
                graph[nx][ny] = 0
                size += 1
                queue.append((nx, ny))
    return size

cnt = 0
max_size = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            cnt += 1
            max_size = max(max_size, bfs(i, j))
print(cnt)
print(max_size)

 (0, 0)부터 (n, m)까지 1인 곳을 bfs 탐색을 합니다.

 지뢰찾기 게임처럼 1인 곳을 발견하면 이어진 부분은 모두 탐색한 뒤 0으로 세팅하기 때문에, cnt를 정확하게 셀 수 있습니다.