[Python] 백준 1926번 그림

문제

1926번: 그림

입력

• 첫째 줄에 도화지의 세로 크기 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/DFS를 수행한다.
• 탐색 중 그림의 크기를 result리스트에 넣는다.
• 탐색이 수행된 횟수가 총 그림의 개수이므로 출력한다.
• 가장 큰 그림의 크기는 그림의 크기가 저장되어있는 result의 가장 큰 값을 출력하면 되고, result의 길이가 0이라면 그림이 0개 있다는 뜻이므로 0을 출력한다.

BFS 코드

from collections import deque
n, m = map(int,input().split())
dy = [-1,1,0,0]
dx = [0,0,-1,1]
visited = [[0] * m for _ in range(n)]
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))

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

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

DFS 코드

import sys
sys.setrecursionlimit(10**6)
n, m = map(int,input().split())
dy = [-1,1,0,0]
dx = [0,0,-1,1]
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))


def dfs(y,x):
    global cnt
    graph[y][x] = 0
    cnt += 1
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < n and 0 <= nx < m and graph[ny][nx] == 1:
            dfs(ny,nx)

result = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            cnt = 0
            dfs(i,j)
            result.append(cnt)

print(len(result))
if len(result) >= 1:
    print(max(result))
else:
    print(0)