[Python] [백준 / BOJ] 1926번 : 그림

📌 문제 링크

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

---

📌 문제 풀이

from collections import deque

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

# 상, 하, 좌, 우 방향 이동
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(x, y):
    q = deque()
    q.append((x, y))          # 시작 좌표 큐에 삽입
    graph[x][y] = 0           # 방문 처리
    area = 0                  # 현재 그림의 넓이

    while q:
        x, y = q.popleft()
        area += 1             # 방문한 칸 수 증가(넓이 갱신)

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위 내이면서 아직 방문하지 않은 그림인 경우
            if nx >= 0 and nx < n and ny >= 0 and ny < m and graph[nx][ny] == 1:
                q.append((nx, ny))
                graph[nx][ny] = 0   # 방문 처리

    return area               # 해당 그림의 넓이 반환

cnt = 0   # 그림의 개수
ans = 0   # 가장 큰 그림의 넓이의 초기값 설정

for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:         # 새로운 그림 발견
            cnt += 1
            ans = max(ans, bfs(i, j))  # BFS로 넓이 계산 후, 가장 큰 그림의 넓이 반환

print(cnt)  # 그림의 개수 출력
print(ans)  # 가장 큰 그림의 넓이 출력

1. 해당 문제는 2차원 배열에서 연결된 영역의 개수와 최대 넓이를 구해야 하므로 BFS를 이용해 접근
2. 먼저 도화지의 크기 n, m과 각 칸의 상태를 graph에 입력받아 저장한 뒤, 방향 벡터 dx, dy를 설정
3. BFS 함수는 아래와 같이 설정
   1. 시작 좌표를 큐에 넣고 방문 처리한 뒤, 큐에서 좌표를 하나씩 꺼내며 좌표가 범위 내에 있다면 연결된 모든 칸을 탐색
   2. 탐색 과정에서 큐에서 좌표를 꺼낼 때마다 방문한 칸 수를 누적하여 하나의 그림이 차지하는 넓이(area)를 계산
   3. 재방문을 방지하기 위해 방문한 좌표의 값은 0으로 변경하여 방문처리 진행
   4. BFS가 종료되면 해당 그림의 넓이를 반환
4. 전체 도화지를 순회하며 값이 1인 칸을 발견할 때마다 새로운 그림으로 판단하여 그림의 개수 증가(cnt)
5. 동시에 위 설정한 BFS 함수와 max 함수 활용하여 가장 큰 그림의 넓이(ans) 갱신
6. 모든 탐색이 끝난 뒤 그림의 개수와 가장 큰 그림의 넓이를 차례대로 출력

---

📖 NOTE

그래프 내에서 모든 경로가 하나로 이어져 있는것이 아니라면, BFS 함수를 정의한 뒤 전체 graph를 순회하며 조건을 만족하는 지점마다 BFS를 실행하고 결과를 누적하는 방식으로 접근해야 함