문제

입력

첫 번째 줄에는 현수막의 크기인 M와 N가 주어진다. (1 ≤ M, N ≤ 250)

두 번째 줄부터 M+1 번째 줄까지 현수막의 정보가 1과 0으로 주어지며, 1과 0을 제외한 입력은 주어지지 않는다.

출력

혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라.

입력 예시 1

8 19
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 1 1 0
0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0
0 1 1 1 1 1 0 1 0 1 0 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

출력 예시 1

3

문제 이해

전형적인 메인에서 DFS호출이 몇번인지 카운트하는 유형이다. 백준에서 실버 난이도의 DFS문제는 이 문제 난이도, 로직을 가지고 있다. 정말 문제 컨셉만 다르지 로직이 동일하다. 그래서 좀 재미가 없다. 아마 실버 난이도로는 이게 한계인가 보다. 하지만 "3184번 양" 문제는 이렇지는 않다. 조금 더 생각할 거리를 주는데 14716번 같은 이런 문제는 좀 아쉽다.

코드

# 백준 14716번 현수막

# 재귀 횟수, 읽는 속도 늘리기
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 방향벡터 위부터 시계방향순
dx = [0, 1, 1, 1, 0, -1, -1, -1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]

def DFS(y, x):
    global graph
    graph[y][x] = 0

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

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

# 0. 입력 및 초기화
M, N = map(int, input().split()) #M세로 N가로
graph = []
cnt = 0

# 1. 연결 정보 입력
for i in range(M):
    graph.append(list(map(int, input().split())))
    
# 2. DFS호출
for i in range(M):
    for j in range(N):
        if graph[i][j]:
            DFS(i, j)
            cnt += 1

# 3. 출력
print(cnt)