[Python] 백준 알고리즘 1926번 - 그림

[Python] 백준 알고리즘 1926번 - 그림

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

1926번: 그림

1926번 - 그림 

 

 접근 방식

전형적인 DFS / BFS 방식의 문제이다. 상하좌우 좌표값을 설정하여 하나의 지점마다 조건에 맞는 부분을 찾아가며 풀어가는 구조이다. 문제에서 구하라는 바는 다음과 같다.

• 1로 이루어진 그림의 개수 -> 0으로 나눠진 부분의 개수를 파악해야 한다
• 각 그림의 크기를 구하며 그 그림의 크기 중 가장 큰 넓이를 찾아라

다음과 같이 2개로 나눠진다.  처음에는 재귀를 활용한 DFS를 사용하여 문제를 풀었지만 재귀의 탐색 제한에 걸려 런타임 에러(RecursionErr)가 발생하였다. 기존 파이썬의 재귀의 한계치를 늘리는 아래와 같은 코드를 입력하였지만 시간 초과에 걸렸다. 그래서 deque를 사용하는 BFS를 활용하여 문제 풀이에 접근하였다.

import sys
sys.setrecursionlimit(10**6)

 구현 코드

# 1926번

from collections import deque

# 세로크기 n, 가로크기 m
n, m = map(int, input().split())

# 리스트 생성
num = []
for i in range(n):
    num.append(list(map(int, input().split())))

visit = [[False] * m for _ in range(n)]

# 이동을 위한 방향
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

cnt = 0  # 그림의 갯수
pic = None
res = 0  # 그림의 크기 비교 후 최댓값

# 체크를 위한 메서드(BFS)

def check2(x, y):
    global pic
    pic = 0

    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()
        pic += 1
        visit[x][y] = True
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if num[nx][ny] == 1 and not visit[nx][ny]:
                    num[nx][ny] = num[x][y] + 1
                    queue.append((nx, ny))
                elif num[nx][ny] == 0:
                    continue


# 문제 풀이를 위한 순회
for i in range(n):
    for j in range(m):
        if num[i][j] == 1 and visit[i][j] != True:
            pic = 0
            check2(i, j)
            cnt += 1
            res = max(res, pic)

print(cnt, res, sep = '\n')

 

 

보충할 점

• java로 풀던 습관이 남아있어 파이썬의 활용에 미숙
• global 변수 활용
• 자료구조에서의 특징으로 나눠지는 DFS / BFS