[Python] 그림 - 백준 (DFS)

해당 글은 백준 1926번 문제 '그림'을 다룬다.

문제

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

1926번: 그림

 

설명

해당 문제는 DFS/BFS로 해결할 수 있고, 필자는 DFS로 구현하였다.

기존에는 지역변수로만 해결하였는데, 전역변수를 통해 더 쉽게 해결하는 방법을 발견하여 해당 코드도 함께 적어둔다.

재귀한계와 관련된 런타임에러가 계속 떴었는데, 이를 아래와 같이 크게 늘려주어야 성공이 뜬다.

sys.setrecursionlimit(1000000)

 

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

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

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

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

result = []
for i in range(n):
    for j in range(m):
        if arr[i][j] == 1:
            result.append(dfs(i, j, 2)-1)

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

   

- 전역변수 사용

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

def dfs(x, y):
    global count        # 전역변수 사용
    arr[x][y] = 2
    count += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
            if arr[nx][ny] == 1:
                dfs(nx, ny)

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

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

result = []
for i in range(n):
    for j in range(m):
        if arr[i][j] == 1:
            count = 0       # 전역변수 초기화
            dfs(i, j)
            result.append(count)

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