[Python 파이썬] 백준 1926번 - 그림

2024년 10월 2일

문제 링크 : 백준 1926번 - 그림

 

문제

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

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

 

문제 접근

 

주어진 도화지는 0과 1로 이루어져 있는데, 가로 혹은 세로로 인접한 1은 하나의 그림으로 간주한다. (대각선은 아님)

 

암시적 그래프 형태로 주어진 도화지에 존재하는 그림의 개수와 가장 큰 그림의 사이즈를 출력하면 되는 문제이다.

 

[0, 0] 좌표부터 [n - 1, m - 1] 좌표까지 순회해보며 값이 1인 좌표를 찾는다면 해당 좌표를 시작점으로 너비 우선 탐색을 진행하는 식으로 로직을 구성하였다.

( 그래프 탐색 이론 : 너비 우선 탐색과 깊이 우선 탐색이란? )

[알고리즘] 깊이우선탐색(DFS), 너비우선탐색(BFS) [ 백준 1260번 - DFS와 BFS ]

 

 

특정 시작점을 기준으로 연결된 모든 1을 찾는다면 해당 집합체는 하나의 그림으로 간주되므로 너비 우선 탐색을 진행한 횟수가 곧 도화지에 존재하는 그림의 개수일 것이다.

 

또한 특정 시작점으로부터 너비 우선 탐색을 진행하며 방문했던 좌표는 0으로 치환해주어 중복 방문을 방지하고자 하였다. 매 탐색마다 탐색한 총 좌표의 개수가 해당 그림의 사이즈이며, 가장 큰 사이즈의 그림을 찾아야 하므로 너비 우선 탐색을 완료할 때마다 해당 그림의 크기가 최대값인지 확인 후 갱신해주어야 한다.

 

여기서 주의해야 할 점은 다음과 같다.

 

단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

 

그림이 하나도 존재하지 않는다면, 그림의 개수는 당연히 0개이다.

허나 그림이 존재하지 않는다고 가장 넓은 그림의 넓이를 출력하지 않는 것이 아닌 0으로 출력하도록 디폴트 값을 설정해주어야 한다.

 

---

입력 예제

 

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

 

 

 

출력 예제

 

4
9

 

---

전체 코드

 

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

def bfs(start_row, start_col):
    size = 0

    queue = deque()
    queue.append([start_row, start_col])
    size += 1
    board[start_row][start_col] = 0

    # 동 남 서 북
    d_row = [0, 1, 0, -1]
    d_col = [1, 0, -1, 0]

    while queue:
        now_row, now_col = queue.popleft()
        for i in range(4):
            next_row, next_col = now_row + d_row[i], now_col + d_col[i]
            if 0 <= next_row < n and 0 <= next_col < m:
                if board[next_row][next_col] == 1:
                    size += 1
                    board[next_row][next_col] = 0
                    queue.append([next_row, next_col])

    return size


def solution():
    cnt = 0
    max_size = 0
    
    for row in range(n):
        for col in range(m):
            if board[row][col] == 1:
                cnt += 1
                max_size = max(max_size, bfs(row, col))

    print(cnt)
    print(max_size)
if __name__ == "__main__":
    n, m = map(int, input().split())
    board = []
    for _ in range(n):
        row = list(map(int, input().split()))
        board.append(row)
    
    solution()

 

 

---

풀이 후기

 

암시적 그래프에서의 탐색을 연습하기 좋은 기본적인 문제였다고 생각한다.