백준 : 1476번 현수막 [DFS, 파이썬]

문제

ANT가 처음 알고리즘 대회를 개최하게 되면서 현수막을 내걸었다.

저번 학기 영상처리 수업을 듣고 배웠던 지식을 최대한 응용 해보고 싶은 혁진이는 이 현수막에서 글자가 몇 개인지 알아보는 프로그램을 만들려 한다.

혁진이는 우선 현수막에서 글자인 부분은 1, 글자가 아닌 부분은 0으로 바꾸는 필터를 적용하여 값을 만드는데 성공했다.

그런데 혁진이는 이 값을 바탕으로 글자인 부분 1이 상, 하, 좌, 우, 대각선으로 인접하여 서로 연결되어 있다면 한 개의 글자라고 생각만 하였다.

혁진이가 필터를 적용하여 만든 값이 입력으로 주어졌을 때, 혁진이의 생각대로 프로그램을 구현하면 글자의 개수가 몇 개인지 출력하여라.

입력

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

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

출력

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

예제 입력 

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

예제 출력

3

 

[문제 풀이]

* 간단한 문제 설명

아래는 예제로 입력된 2차원 배열에서 글자를 나타내는 부분 '1'을 표시한 것이다.

상, 하, 좌, 우, 대각선으로 인접하여 서로 연결되어 있다면 한 개의 글자이다. => 크게 A,N,T모양처럼 표시된 부분을 한개의 글자로 본다.

따라서 예제의 글자의 개수는 3개이다.

 

* 풀이 방법

: 깊이 우선 탐색, DFS를 사용한다. -> 문제는 서로 연결되어있는 관계를 찾아야한다. 따라서 깊이 우선탐색, 혹은 너비우선 탐색이 필요하다. 이 두 가지 알고리즘은 인접 노드들을 탐색하며 연결 관계를 찾을 수 있다.

 

나는 깊이 우선 탐색으로 풀었다.

 

대략적인 순서:

1. 0이 아닌 노드들을 찾는다. 

2. 연결되어있는 1을 끝까지 찾으며 1인 노드들을 0으로 바꾸어주면 될 것 같다. (여기서 깊이 우선 탐색을 활용한다.)

3. 연결이 끝날 때마다 카운트를 세주어 글자수를 확인한다.

 

* 코드 작성

import sys
sys.setrecursionlimit(10 ** 6)  # 재귀 허용 깊이를 수동으로 늘려줌

# dfs 탐색
def dfs(x, y):

    if x <= -1 or x >= M or y <= -1 or y >= N:
        return False

    if graph[x][y] == 1: # 탐색하지 않았으면 탐색
        # 탐색했으면 0
        graph[x][y] = 0
        # 상,하,좌,우,대각선을 재귀적으로 탐색
        dfs(x + 1, y) # 오른쪽
        dfs(x + 1, y + 1) # 오른쪽 위 대각선
        dfs(x + 1, y - 1) # 오른쪽 아래 대각선
        
        dfs(x - 1, y) # 왼쪽
        dfs(x - 1, y + 1) # 왼쪽 위 대각선
        dfs(x - 1, y - 1) # 왼쪽 아래 대각선
        
        dfs(x, y + 1) # 위
        dfs(x, y - 1) # 아래

        return True
    return False

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

count = 0 # 글자 개수

for i in range(M):
    for j in range(N):
        if graph[i][j] == 1:
            dfs(i, j)

            # 글자 개수 카운트
            count += 1
print(count)