[백준 4963] 섬의 개수 파이썬 풀이 - BFS

[백준 4963] 섬의 개수 파이썬 풀이 - BFS

문제

문제 링크 : 백준 4963

---

접근

전형적인 BFS 문제라고 할 수 있다.

기존 비슷한 다른 문제를 풀어봤을 땐 상,하,좌,우만 생각했다면
이번 문제는 상,하,좌,우 와 더해서 좌상, 우상, 좌하, 우하도 고려한다.

위와 같을 때 섬은 두 개이다.

• 따라서 2차원 리스트에서 1로 칠해져있는 곳을 너비우선탐색하여 방문한 곳은 0으로 바꾸어주도록 한다.
• 해당 노드에서 인접한 모든 곳을 방문을 마쳤다면 count를 1만큼 올려주어 섬의 개수를 센다.

---

풀이

위에서 접근한 방식을 그림으로 풀어본다면,
w = 3, h = 4 이며 첫번째와 같이 주어졌을 때 한 사이클은 이렇게 돌 것이다.

섬 한 개를 찾았으니 count는 1만큼 증가하고, 섬 하나는 0(바다)으로 지워지고, 남은 섬을 찾아 두번째 사이클을 돈다.

두번째 사이클이 돌면 또 다른 섬을 찾았으니 count는 2만큼 증가한다.
그리고 모든 곳이 0이기 때문에 더이상 섬을 찾을 수 없다. 따라서 섬은 2개이다.

정답 코드

# 4963
from collections import deque


def bfs(x, y):
  queue = deque()
  queue.append((x, y))
  while queue:
    x, y = queue.popleft()
    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]
      if -1 >= nx or nx >= h or -1 >= ny or ny >= w:
        continue
      if a[nx][ny] == 0:
        continue
      if a[nx][ny] == 1:
        a[nx][ny] = 0
        queue.append((nx, ny))


w, h = map(int, input().split())

a = []
while not (w == 0 and h == 0):
  count = 0
  for i in range(h):
    a.append(list(map(int, input().split())))
  # 방향을 dx,dy로 저장해두고 nx,ny에서 활용하기가 좋다.
  dx = [0, 0, 1, -1, 1, 1, -1, -1]
  dy = [1, -1, 0, 0, 1, -1, 1, -1]
  for i in range(h):
    for j in range(w):
      if a[i][j] == 1:
        bfs(i, j)
        count += 1
  print(count)
  a = []
  w, h = map(int, input().split())

코드를 실행하면 아래처럼 결과가 나온다.

---

느낀점

많이 접해본 BFS문제인데 대각선 방향도 추가된 점이 살짝 다르다.
dx,dy 배열에 대각선 방향만을 추가해준다면 쉽게 풀 수 있을 것이라고 생각된다.
요즘 문제가 잘풀려서 행복하다..ㅎㅎㅎ