[Python/파이썬] 백준 14716번 현수막

14716번: 현수막

 

코드

from collections import deque

m, n = map(int, input().split())
input_data = [list(map(int, input().split())) for _ in range(m)]

move = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
visited = [[False]*n for _ in range(m)]
char_num = 0
for i in range(m):
    for j in range(n):
        if input_data[i][j] == 1 and not visited[i][j]:
            q = deque([(i, j)])
            visited[i][j] = True
            while q:
                x, y = q.popleft()
                for d in range(8):
                    nx = x+move[d][0]
                    ny = y+move[d][1]
                    if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and input_data[nx][ny] == 1:
                        visited[nx][ny] = True
                        q.append((nx, ny))
            char_num += 1
print(char_num)

 

아직 방문 안 한 1이 등장할 때 마다 BFS를 수행하여 같은 글자에 속한 1들을 모두 방문처리해주면 된다. 현수막 입력값의 처음부터 끝까지 이렇게 BFS를 수행한 횟수를 세면 그게 바로 현수막에 있는 글자 수이다.