[백준] 14716 - 현수막

1. 문제

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

14716번: 현수막

 

2. 접근

1. '이코테 - 음료수 얼려먹기' 의 로직과 일치한다. 다만 대각선을 대비해준다

-> board[x][y]이 1일때 글자가 이어지는 부분임을 인지해서 재귀적으로 dfs()를 호출해준다

2. 재귀함수가 대각선이 추가됨으로써 RecursionError를 대비해야 한다

 

3. 풀이

#14716 실버1
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n,m = map(int,input().split())

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

def dfs(x,y):
    if 0<=x<n and 0<=y<m and board[x][y] == 1:
        board[x][y] = 2
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y-1)
        dfs(x,y+1)
        dfs(x-1,y-1)
        dfs(x-1,y+1)
        dfs(x+1,y-1)
        dfs(x+1,y+1)
        return True
    return False

cnt = 0
for i in range(n):
    for j in range(m):
        if dfs(i,j) == True:
            cnt += 1
print(cnt)