[백준 14716] 현수막(Python)

1. 요약

글자인 부분을 의미하는 1이 상, 하, 좌, 우, 대각선으로 서로 인접하면 이들은 모두 1개의 글자로 간주한다. 이 때, 주어진 현수막에서 몇 개의 글자가 있는지 찾아보자.

2. 아이디어

현수막의 부분을 탐색하다가, 방문하지 않은 1를 발견하면, 글자의 수를 하나 증가시키고 BFS를 실시한다.

3. 코드

import sys
from collections import deque

r, c = map(int, sys.stdin.readline().rstrip().split())
d = [[-1,0], [1,0], [0,1], [0,-1], [-1,-1], [-1,1], [1,-1], [1,1]]
arr = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(r)]
visited = [[False for _ in range(c)] for _ in range(r)]

def isin(y,x):
    if -1<y<r:
        if -1<x<c: return True
    return False

def bfs(sy, sx):
    q = deque()
    q.append([sy, sx])
    visited[sy][sx] = True

    while q:
        y, x = q.popleft()

        for i in range(8):
            ny = y + d[i][0]
            nx = x + d[i][1]

            if isin(ny, nx):
                if not visited[ny][nx]:
                    visited[ny][nx] = True
                    if arr[ny][nx] == 1:
                        q.append([ny,nx])

cnt = 0

for i in range(r):
    for j in range(c):
        if not visited[i][j] and arr[i][j] == 1:
            cnt += 1
            bfs(i, j)

print(cnt)