[Python] 14716번 현수막

✏️ 문제

 

문제 파악

글자인 부분 1이 상, 하, 좌, 우, 대각선으로 인접하여 서로 연결되어 있다면 한 개의 글자라고 생각하므로 다음과 같이 방향 배열을 구성했다.

d = [(-1, 0), (0, 1), (1, 0), (0, -1), (-1, -1), (-1, 1), (1, 1), (1, -1)]

 

글자의 개수를 구하는 것이므로 BFS가 한 번 돌면 한 글자이므로 돌 때마다 +1 하면 글자의 개수가 나온다.

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

 

코드

from collections import deque

m, n = map(int, input().split())
graph = [[0] * n for _ in range(m)]
visited = [[0] * n for _ in range(m)]
d = [(-1, 0), (0, 1), (1, 0), (0, -1), (-1, -1), (-1, 1), (1, 1), (1, -1)]
cnt = 0 

for i in range(m):
  line = list(map(int, input().split()))
  for j in range(n):
    graph[i][j] = line[j]

    if line[j] == 0:
      visited[i][j] = -1

def bfs(x, y):
  q = deque([(x, y)])
  visited[x][y] = 1
  
  while q:
    x, y = q.popleft() 

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

      if 0 <= dx < m and 0 <= dy < n and visited[dx][dy] == 0:
        visited[dx][dy] = 1
        q.append([dx, dy])
        
for i in range(m):
  for j in range(n):
    if visited[i][j] == 0:
      bfs(i, j)
      cnt += 1

print(cnt)

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS