백준 1926번: 그림(DFS)

BOJ

백준 1926번: 그림

문제

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

접근

그림의 개수
그림 중 가장 넓은 것의 넓이

백준 1743번: 음식물 피하기 음식물 피하기에서 음식물의 크기를 구했던 것처럼 그림의 넓이를 구하면 될 거 같다. 위의 문제와 차이점은 그림의 개수를 구하는 것이다.

재귀를 활용해서 DFS로 문제를 풀었지만 메모리 초과가 발생했다. sys.setrecursionlimit(10**6) 블로그 검색을 통해 앞의 코드를 sys.setrecursionlimit(15000)로 고쳤지만, 재귀의 탐색 제한에 걸려 런타임 에러(RecursionErr)가 발생하였다.

여러 블로그들의 글들을 들어가서 읽어보니 이 문제는 DFS보다는 BFS로 푸는 게 더 쉬운 문제였다.
메모리 초과를 해결하기 위해서 global cnt 전역 변수를 사용했고, 방향 이동을 for문으로 구현하지 않았다.

Correct Solution 코드 밑에 Wrong Solution 코드도 같이 올려놓습니다. 문제 풀 때 참고하세요.

Correct Solution

# dfs 함수
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(y, x):
    global cnt

    if 0 > y or y >= N or 0 > x or x >= M:
        return False

    if graph[y][x] == 1:

        graph[y][x] = 0
        cnt += 1

        dfs(y + 1, x)
        dfs(y, x + 1)
        dfs(y - 1, x)
        dfs(y, x - 1)

        return True

    return False

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

# 방향벡터를 사용해서 for문을 돌리면 메모리 초과 에러 메시지가 나온다.
#dy = [1, 0, -1, 0]
#dx = [0, 1, 0, -1]

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

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

Wrong Solution

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

#sys.setrecursionlimit(10**6) 메모리 초과
#sys.setrecursionlimit(15000) 런타임 에러 (RecursionError)

def dfs(y, x):
    global cnt
    cnt += 1

    graph[y][x] = 0

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if 0 <= ny < N and 0 <= nx < M:
            if graph[ny][nx] == 1:
                dfs(ny, nx)

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

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

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

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

참고 사이트

천천히 꾸준하게 BAEKJOON 1926번-그림 질문