[백준] 14726번: 현수막 (python)

14726번: 현수막

---

문제 )

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

 

 

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

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

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

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

 

 

 

입력 :

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

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

 

 

 

출력 :

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

 

 

풀이)

DFS, BFS가 모두 가능한 문제.

문제에서 제시한 것처럼 8방향 탐색을 해주었으며, 재귀를 이용한 DFS로 풀었기 때문에

재귀 제한이 걸려 sys를 이용해 재귀 깊이 제한을 어느정도 풀어주었다.

 

import sys
sys.setrecursionlimit(1 << 20)
 
# x, y가 범위 안에서 놀도록
def in_range(x, y):
    return -1 < x < n and -1 < y < m
 
def dfs(a, b):
    visited[a][b] = 1
 
    for i in range(8):
        x = a + di[i]
        y = b + dj[i]
        if in_range(x, y) and not visited[x][y] and g[x][y]:
            dfs(x, y)
 
n, m = map(int, input().split())
g = [list(map(int, input().split())) for i in range(n)]
visited = [[0] * m for i in range(n)]
 
# DFS, BFS 모두 상관 없음.
# 플러드 필 문제
 
di = [-1, 1, 0, 0, -1, -1, 1, 1] # 8방향 탐색
dj = [0, 0, -1, 1, -1, 1, -1, 1]
 
cnt = 0
for i in range(n):
    for j in range(m):
        if g[i][j] and not visited[i][j]:
            cnt += 1
            dfs(i, j)
print(cnt)

 

---

출처 : https://www.acmicpc.net/problem/14716

14716번: 현수막