백준[ 1926 | Python ] 그림

문제

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

풀이

메모리에 관한 문제가 있어 BFS와 스택을 이용한 DFS로 문제를 해결했다.
가로나 세로로 연결된 것은 연결된 것이고 대각선으로 연결된 것은 떨어진 것이라는 조건을 유념하여 방향을 미리 설정해준다.
이후 BFS나 DFS로 그래프를 탐색하여 그 넓이를 배열에 저장해 해결한다.

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

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

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

def dfs(x,y):
    global cnt
    cnt+=1
    graph[x][y] = 0
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0<=nx<n and 0<=ny<m and graph[nx][ny] == 1:
            dfs(nx,ny)

def bfs(x,y):
    global cnt
    q = deque()
    q.append((x,y))
    while q:
        qx,qy = q.popleft()
        for i in range(4):
            nx,ny = qx+dx[i], qy+dy[i]
            if 0<=nx<n and 0<=ny<m and graph[nx][ny] == 1 and not v[nx][ny]:
                cnt+=1
                v[nx][ny] = 1
                q.append((nx,ny))

def dfs_stack(x,y):
    global cnt
    stack = [(x,y)]
    while stack:
        sx,sy = stack.pop()
        for i in range(4):
            nx,ny = sx+dx[i],sy+dy[i]
            if 0<=nx<n and 0<=ny<m and graph[nx][ny] == 1 and not v[nx][ny]:
                cnt+=1
                v[nx][ny] = 1
                stack.append((nx,ny))        

lst = []
v = [[0]*m for _ in range(n)]

# for i in range(n): 재귀를 이용한 DFS는 시간초과가 난다.
#     for j in range(m):
#         if graph[i][j]==1:
#             cnt = 0
#             dfs(i, j)
#             lst.append(cnt)

# for i in range(n): BFS를 이용한 풀이는 35012KB, 620ms가 소요되었다.
#     for j in range(m):
#         if graph[i][j] == 1 and not v[i][j]:
#             cnt = 1
#             graph[i][j] = 0
#             bfs(i, j)
#             lst.append(cnt)

for i in range(n): # 스택으로 구현한 DFS는 46344KB, 616ms가 소요되었다.
    for j in range(m):
        if graph[i][j] == 1 and not v[i][j]:
            cnt = 1
            graph[i][j] = 0
            dfs_stack(i, j)
            lst.append(cnt)

if not lst:
    print(f"{len(lst)}\n0")
else:
    print(f"{len(lst)}\n{max(lst)}")

생각 & 정리

BFS를 사용하는가 DFS를 사용하는가는 solution이 root로 부터 얼마나 떨어져있는가로 부터 결정된다.

root로 부터 얕은 층에 존재하는 solution을 해결하려할 때 DFS를 사용하게 된다면, 특히 이를 재귀로 구현하게 된다면 더욱 많은 시간과 메모리를 사용하게 된다.

이는 반대의 경우에도 마찬가지지만, deque를 이용하는 BFS보다는 큰 차이를 보이지는 않을 것이라는 생각이 들었다.

따라서 DFS를 stack으로 구현해보았다면 결과가 달라졌을 수 있지 않았을까 하는 의문점이 생겼고 이를 구현했다.

결과는 더 많은 메모리의 사용과 무의미 하지만 더 적은 시간(04ms)의 차이가 났다.

해당 문제는 root로 부터 solution이 비교적 그렇게 깊지 않은 층에 존재했던 것 같다.(물론 두 쪽다 존재하는 문제였지만 DFS보다는 BFS 카테고리에 들어가야하는 문제가 아니었을까?)

항상 그래프 탐색 문제를 마주할때면 깊이를 우선해야할지 너비를 우선해야할지 조금의 고민을 하다가 문제를 해결하는데, 이를 판단할 수 있는 능력이 생기면 접근 방법을 선택하는데에 큰 도움이 될 것 같다는 생각이 들었다.