[백준] #1926. 그림 (python) - bfs 풀이

문제

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

1926번: 그림

 

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

 

입력

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

 

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 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

 

 

풀이 - BFS

 

이 문제는 BFS(너비 우선 탐색)을 사용해서 풀었다.

 

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())

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

graph = []

for _ in range(n):
    paints = list(map(int, sys.stdin.readline().split()))
    graph.append(paints)

def bfs(sy, sx):
    
    q = deque([])
    q.append([sy, sx])
    visited[sy][sx] = True
    cnt = 1

    while q:
        y, x = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if (0 <= nx < m) and (0 <= ny < n) and graph[ny][nx] == 1 and visited[ny][nx] == 0:
                q.append([ny, nx])
                visited[ny][nx] = 1
                cnt += 1
    return cnt

results = []
visited = [[0]*m for _ in range(n)]

for j in range(0, n):
    for k in range(0, m):
        if graph[j][k] == 1 and visited[j][k] == 0:
            cnt = bfs(j, k)
            results.append(cnt)

print(len(results))
if len(results) == 0:
    print(0)
else:
    print(max(results))

 

 

이 문제에서 입력으로 세로, 가로가 주어진다. 세로가 먼저인 이유는 그림을 좌표로 접근할 때 [세로][가로] 순으로 접근해야 하기 때문이다.

bfs 구현 부분을 보면 모두 graph[y][x] 순으로 접근한다.

 

1. 탐색 범위 세팅

가로나 세로로 연결된 그림을 연결된 것으로 보기 때문에 탐색 범위는 상하좌우다.

dx, dy를 정의해서 상하좌우로 탐색하기 위한 세팅을 한다.

 

2. bfs 함수 구현

우선 처음 탐색을 시작하는 좌표에 대해 방문 여부를 표시한다. 그리고 그림의 넓이를 계산하기 위해 cnt 값을 1로 세팅한다.

1에서 정의한 탐색범위를 모두 탐색하면서 다음으로 탐색할 좌표들을 찾는다.

 

🔹if문 조건

- 인덱스 범위 안에 해당하는가

- 그림이 색칠되어 있는가 (값이 1이어야 함)

- 아직 방문하지 않았는가

 

위 조건들을 모두 만족한다면 해당 좌표를 큐에 추가한다. 그리고 방문여부를 체크하고 넓이에 1을 더한다.

 

3. [0,0] 부터 bfs 진행

그림의 어떤 부분이 1일지 모르니까 0, 0부터 순서대로 그림이 색칠되어있는지와 방문 여부를 확인한다.

그림이 색칠되어있고 아직 방문하지 않았다면 bfs를 호출해 탐색을 진행한다.

탐색이 끝나면 results 변수에 그림의 최종 넓이를 추가한다.

 

4. 결과 출력

그림의 개수가 0인 경우와 아닌 경우를 구분해 결과값을 출력한다.