이번 문제는 깊이우선탐색을 통해 해결하였다. 섬의 분포를 확인하기 위해 총 8개의 방향으로 나아갈 수 있기 때문에 dw, dh 리스트를 만들어 8가지의 방향을 저장한 후 이 방향을 이용해서 연결될 수 있는 섬을 모두 방문처리한다. 현재 섬이 이미 방문처리 되어있을 경우 넘어가고 방문처리 되어있지 않을 때만 섬 연결을 확인한다. 섬의 연결 확인을 시작할 때 카운팅을 1 늘려준다. 이 방법은 연결 된 모든 섬을 방문처리하여 방문처리를 몇번 했는지 체크하는 방식이다.

첫 시도 시 재귀 에러가 발생하였다. 찾아본 결과 백준에서의 최대 재귀 횟수를 초과하면 발생하는 에러라고 한다. 그래서 sys.setrecursionlimit(10**9)를 선언하여 최대 재귀 횟수를 늘려주어 해결하였다.

• 최대 재귀 횟수를 늘려준다.
• 무한 반복하는 while문을 돌린다.
• w와 h를 입력받는다.
• 만약 w와 h가 모두 0이라면 while문을 탈출한다.
• 지도를 저장하는 리스트 island를 선언한다.
• 방문처리에 사용할 리스트 visited를 h*w개의 False로 선언한다.
• 8가지의 방향을 저장할 리스트 dw, dh를 선언하고 8개의 방향을 짝지어 저장한다.
• 섬의 개수를 셀 변수 cnt를 0으로 선언한다.
• dfs 함수를 w_tmp, h_tmp를 인자로 갖도록 선언한다.
  -> visited[h_tmp][w_tmp]를 True로 갱신한다.
  -> 8번 반복하는 i에 대한 for문을 돌린다.
  --> 검사할 좌표를 저장하는 변수 next_w, next_h를 선언하고 w_tmp+dw[i], h_tmp+dh[i]를 저장한다.
  --> 만약 next_w와 next_h가 0보다 크고, next_w가 w보다 작고, next_h가 h보다 작을 경우,
  ---> 만약 visited[next_h][next_w]가 False이고 island[next_h][next_w]가 1이라면 dfs(next_w, next_h)를 재귀호출한다.
• h번 반복하는 i에 대한 for문을 돌린다.
  -> island를 입력한다.
• h번 반복하는 i에 대한 for문을 돌린다.
  -> w번 반복하는 j에 대한 for문을 돌린다.
  --> 만약 island[i][j]가 1이고 visited[i][j]가 False라면 dfs(i, j)를 호출하고 cnt를 1 증가시킨다.
• cnt를 출력한다.

Code

import sys
sys.setrecursionlimit(10**9)
while True:
    w, h=map(int, input().split())
    if w==0 and h==0:
        break
    island=[]
    visited=[[False]*w for _ in range(h)]
    dh=[1, -1, 0, 0, 1, 1, -1, -1]
    dw=[0, 0, 1, -1, 1, -1, 1, -1]
    cnt=0
    def dfs(w_tmp, h_tmp):
        visited[h_tmp][w_tmp]=True
        for i in range(8):
            next_w=w_tmp+dw[i]
            next_h=h_tmp+dh[i]
            if next_w>=0 and next_h>=0 and next_w<w and next_h<h:
                if visited[next_h][next_w]==False and island[next_h][next_w]==1:
                    dfs(next_w, next_h)
    for i in range(h):
        island.append(list(map(int, input().split())))
    for i in range(h):
        for j in range(w):
            if island[i][j]==1 and visited[i][j]==False:
                dfs(j, i)
                cnt+=1
    print(cnt)