[백준/python] 1926 : 그림

문제

 

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

---

Algorithm

1. dfs 알고리즘을 이용해 한 그림 즉 1이 이어져있는 것을 찾는다.

2. 찾는 과정에서 정수 e를 전역변수로 두고 그림의 크기를 기록해 가장 큰 그림의 크기를 구한다.

3. dfs 알고리즘을 통해 그림을 하나 찾을 때 마다 정수 cnt를 활용해 그림의 개수를 구한다.

 

---

 

 

Code

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


def dfs(x, y):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    global e


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


        if (0 <= nx < m) and (0 <= ny < n) and graph[ny][nx] == 1:
            graph[ny][nx] = -1
            e += 1
            dfs(nx, ny)



n, m = map(int,input().split())
graph = []

for _ in range(n):
    te = list(map(int,input().split()))
    graph.append(te)

M = 0
cnt = 0
for a in range(m):
    for b in range(n):
        if graph[b][a] == 1:
            e = 1
            graph[b][a] = -1
            dfs(a, b)
            cnt += 1
            temp = e
            if temp > M:
                M = temp

print(cnt)
print(M)