[Python] 11123번 양 한마리... 양 두마리...

✏️ 문제

 

문제 파악

상하좌우 4가지가 붙어있으면 하나의 무리가 되므로 다음과 같이 방향 배열을 구성했다.

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

 

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

 

알고리즘

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

 

 

코드

from collections import deque
import sys
input = sys.stdin.readline

for _ in range(int(input())):
  h, w = map(int, input().split())
  graph = [[0] * w for _ in range(h)]
  visited = [[0] * w for _ in range(h)]
  d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
  num = 0

  for i in range(h):
    s = input()
    for j in range(w):
      if s[j] == '#':   # 양
        graph[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(4):
        dx = x + d[i][0]
        dy = y + d[i][1]

        if 0 <= dx < h and 0 <= dy < w and visited[dx][dy] == 0 and graph[dx][dy] == 1:
          visited[dx][dy] = 1
          q.append([dx, dy])

  for i in range(h):
    for j in range(w):
      if visited[i][j] == 0 and graph[i][j] == 1:
        bfs(i, j)
        num += 1

  print(num)

 

 

---

 

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

[알고리즘] DFS와 BFS