1. 문제

---

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

출처 : https://www.acmicpc.net/problem/4963

2. 아이디어

---

• 단지번호붙이기에서 구현한 dfs에 대각선만 추가시킨다.

3. 코드

---

mine

# DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x,y):
  # 주어진 범위를 벗어나는 경우 즉시 종료
  if x <= -1 or x >= h or y <= -1 or y >= w:
    return False
  # 현재 노드를 아직 방문하지 않았다면
  if graph[x][y] == 1:
    # 해당 노드 방문 처리와 함께 카운트
    graph[x][y] = 0
    # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
    dfs(x-1, y)
    dfs(x, y-1)
    dfs(x+1, y)
    dfs(x, y+1)
    dfs(x+1, y+1)
    dfs(x+1, y-1)
    dfs(x-1, y+1)
    dfs(x-1, y-1)
    return True
  return False

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break

    graph = [list(map(int, input().split())) for _ in range(h)]
  
    count = 0

    for i in range(h):
      for j in range(w):
        # 현재 위치에서 DFS 수행
        if dfs(i, j) == True:
          count += 1
    print(count)