[그래프 탐색] 백준 4963 파이썬 (섬의 개수) 실버2

-풀이

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
while True:
  #w = 너비 h = 높이
  island = 0
  w, h = map(int, input().split())
  if w == 0 and h == 0:
    break
  graph = []
  #섬 높이만큼 반복
  for i in range(h):
    graph.append(list(map(int, input().split())))

  dx = [0, 0, 1, -1, 1, 1, -1, -1]
  dy = [1, -1, 0, 0, 1, -1, 1, -1]
  def DFS(x, y):
    #x는 높이(h)보다 크면 안되고, y는 너비(w))보다 크면 안된다.
    if x < 0 or x >= h or y < 0 or y >= w:
      return False
    #섬(1)이 있으면 가로,세로, 대각선 탐색 후 True 리턴
    if graph[x][y] == 1:
      graph[x][y] = 0
      for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        DFS(nx, ny)
      return True
    return False
  for i in range(h):
    for j in range(w):
      if DFS(i,j) == True:
        #섬 개수
        island += 1
  print(island)
   

-풀이 설명

[30분 sol] 이전에 푼 2667 단지번호붙이기 문제를 참고해서 해결했다. 2667문제는 가로 세로를 탐색하여 단지와 집 개수를 찾는 것이었고, 이 문제는 조금 응용되어 가로,세로,대각선까지 찾아서 섬의 개수를 출력을 하면 된다. 이전에서 계속 풀었던 문제들은 거의 가로와 세로너비가 똑같았는데, 이 문제는 w(너비) h(높이)로 구분해줘야 해서 dfs함수를 실행할 때 약간 헷갈려 코드를 조금 수정한 부분이 있었다. 하지만 덕분에 dfs가 어떤식으로 동작하는지 더 자세하게 알게 되었다.

https://dlwns7267.tistory.com/302

[그래프 탐색] 백준 2667 파이썬 (단지번호붙이기) 실버1