👩‍💻🔭 [baekjoon] 1962번: 그림

🖍️ solution

import sys
from collections import deque
from typing import List

"""
[시간]
1) 16:50 ~ 17:20
[요약]
1) 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력
    - 영역 구분 및 넓이가 가장 큰 영역의 넓이 구하는 프로그램 작성
    - 상하좌우 1로 연결된 것이 그림
[전략]
1) BFS
    - 시간은 넉넉함
    - 조건문에서 다중조건 쓸 때 순서 유의해서 작성하기
"""
def bfs(y: int, x: int, visit: List[bool]) -> int:
    visit[y][x] = True
    queue = deque()
    queue.append([y, x])
    count = 1
    while queue:
        vy, vx = queue.popleft()
        for i in range(4):
            ny = dy[i] + vy
            nx = dx[i] + vx
            if -1 < ny < N and -1 < nx < M and paper[ny][nx] == 1 and not visit[ny][nx]:
                visit[ny][nx] = True
                queue.append([ny, nx])
                count += 1
    return count

N, M = map(int, sys.stdin.readline().split())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
visited = [[False]*M for _ in range(N)]

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

result = []
for i in range(N):
    for j in range(M):
        if paper[i][j] == 1 and not visited[i][j]:
            result.append(bfs(i, j, visited))

print(len(result))
print(max(result) if len(result) != 0 else 0)

💡 idea

• 1) BFS로 풀이
  • 테이블 형태로 자료구조가 주어지면 BFS로 접근하는게 좀 더 편리
    • 특히 영역 분할, 넓이 구하는 문제는 BFS가 유리
    • recursionlimit 도 피할 수 있음
  • 조건문에서 다중 조건 사용할 때, 순서 유의해서 조건 나열하기
    • 순서 맘대로 막하면 IndexError 발생
  • 도화지에 그림이 없는 경우 예외처리

🧪 experiement

Experiment Result

첫번째 풀이 제출은 메서드에 visited 변수를 지역 변수로 할당하고 사용한 결과고, 두번째 풀이 제출은 전역 변수 처리하고 얻은 결과다. 전자가 메모리를 덜 소비하며, 연산 역시 더 빠른 모습이다. 반드시 메서드에서 사용할 변수들은 모두 스택에 할당해 지역 변수로 사용하자.