[백준] 1926 - 그림

문제

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

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 

단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

 

 

풀이

BFS 방식으로 풀어낼 수 있는 문제이다.

 

1. 입력값  초기화

입력으로 받는 n과 m, 그리고 그림을 초기화한다.

n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for i in range(n)]

 

2. 그림칸 방문 여부를 저장할 visited와 그림의 수를 저장할 cnt를 선언

그림의 모든 칸을 순회하면서 BFS를 수행할 필요가 있으므로, 기존 수행 내용을 저장할 변수를 선언한다.

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

vistied는 그림의 크기를 저장할 수 있도록 그림과 동일한 형태의 리스트로 선언했다.

 

3. BFS 구현

그림을 순회하면서 수행할 BFS를 구현한다.

def bfs(graph, n, m, visited, cnt=0, start=(0, 0)):
    # 그림 시작점의 연결 여부 및 방문 여부 확인
    if graph[start[0]][start[1]] == 0 or visited[start[0]][start[1]] != 0:
        return visited, cnt

    # 시작점을 큐에 넣음
    queue = [start]
    # 방문할 방향 선언
    directions = [(1, 0), (0, -1), (-1, 0), (0, 1)]
    # 그림의 수와 크기 선언
    cnt += 1
    size = 1
    # visited의 시작점의 크기 저장
    visited[start[0]][start[1]] = size

    while queue:
        # 현재 칸
        i, j = queue.pop(0)

        # 방문
        for x, y in directions:
            ni, ny = i + x, j + y

            # 그림의 인덱스 및 연결 여부 확인
            if 0 <= ni < n and 0 <= ny < m and graph[ni][ny] == 1:
                # 방문한 적이 없으면 방문 목록에 저장
                if visited[ni][ny] == 0:
                    queue.append((ni, ny))
                    size += 1
                    visited[ni][ny] = size

    return visited, cnt

 

4. 그림을 순회하며 BFS 수행

for i in range(n):
    for j in range(m):
        visited, cnt = bfs(graph, n, m, visited, cnt, start=(i, j))

 

5. 출력

마지막으로 그림의 수를 나타내는 cnt를 출력하고, 그림의 크기를 저장하는 visited 값에서 최댓값을 출력한다.

print(cnt)
print(max(sum(visited, [])))

 

전체 코드는 접은글로 적어둔다.

import sys

def bfs(graph, n, m, visited, cnt=0, start=(0, 0)):
    if graph[start[0]][start[1]] == 0 or visited[start[0]][start[1]] != 0:
        return visited, cnt

    queue = [start]
    directions = [(1, 0), (0, -1), (-1, 0), (0, 1)]
    cnt += 1
    size = 1
    visited[start[0]][start[1]] = size

    while queue:
        i, j = queue.pop(0)

        for x, y in directions:
            ni, ny = i + x, j + y

            if 0 <= ni < n and 0 <= ny < m and graph[ni][ny] == 1:
                if visited[ni][ny] == 0:
                    queue.append((ni, ny))
                    size += 1
                    visited[ni][ny] = size

    return visited, cnt

n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
visited = [[0 for _ in range(m)] for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(m):
        visited, cnt = bfs(graph, n, m, visited, cnt, start=(i, j))

print(cnt)
print(max(sum(visited, [])))

 

 

참고 문서

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