백준 1926 그림 (Python / 파이썬)

본 글은 작성자가 직접 푼 코드를 바탕으로 Chat-GPT를 활용하여 포스팅한 글입니다.

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

문제

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

문제 이해

주어진 문제에서는 2차원 배열에 그림이 그려져 있고, 그림은 1로 연결된 영역을 의미한다. 그림의 개수와 가장 큰 그림의 넓이를 구해야 한다.

입력

• 정수 n, m (1 ≤ n, m ≤ 500)
• n개의 줄에는 각각 m개의 정수로 이루어진 2차원 배열

출력

• 그림의 개수와 가장 큰 그림의 넓이

해결 방법

주어진 문제를 해결하기 위해서는 다음과 같은 방법을 사용할 수 있다.

1. 그림의 개수와 최대 넓이를 저장할 변수를 초기화한다.
2. 2차원 배열을 순회하면서 방문하지 않은 1을 찾는다.
3. 방문하지 않은 1을 찾으면 BFS나 DFS를 사용하여 그림의 넓이를 계산한다.
4. 계산된 넓이가 최대 넓이보다 크면 최대 넓이를 업데이트한다.
5. 그림의 개수를 증가시킨다.
6. 모든 순회가 끝나면 그림의 개수와 최대 넓이를 출력한다.

주어진 코드에서는 입력으로 주어진 2차원 배열을 순회하면서 방문하지 않은 1을 찾고, BFS를 사용하여 그림의 넓이를 계산하고 최대 넓이를 업데이트하는 로직을 포함하고 있다.

• 입력으로 주어진 2차원 배열을 순회하면서 방문하지 않은 1을 찾는다.
• 방문하지 않은 1을 찾으면 BFS를 사용하여 그림의 넓이를 계산한다.
• 계산된 넓이가 최대 넓이보다 크면 최대 넓이를 업데이트한다.
• 그림의 개수를 증가시킨다.
• 마지막으로 그림의 개수와 최대 넓이를 출력한다.

전체 코드

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

def bfs(x,y, visited):
    q = [(x,y)]
    visited[x][y] = True
    dx, dy = [1,-1,0,0], [0,0,1,-1]
    size = 1
    while q:
        x,y = q.pop(0)
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if nx >= n or nx < 0 or ny >= m or ny < 0:
                continue
            if map_list[nx][ny] == 0 :
                continue
            if visited[nx][ny]:
                continue
            q.append((nx,ny))
            visited[nx][ny] = True
            size += 1
    return size

visited = [[False]*m for _ in range(n)]
scale = 0
cnt = 0
for i in range(n):
    for j in range(m):
        if map_list[i][j] == 1 and visited[i][j] == False:
            tmp = bfs(i,j, visited)
            scale = max(scale, tmp)
            cnt += 1
print(cnt)
print(scale)