# 4963번: 섬의 개수

import sys
sys.setrecursionlimit(10000000)

def island(w,h):

    graph = []
    for i in range(h):
      graph.append( list(map(int,sys.stdin.readline().split()))) 

    move_x = [ -1, 1, 0, 0, -1,-1,1,1 ]  # x는 세로, 순서대로 가로 세로 대각선 
    move_y = [ 0, 0, -1, 1, -1,1,-1,1 ]  # y는 가로
    
    def dfs ( x,y ) : 
        graph[x][y] = 0

        for i in range(8):
            nx = x + move_x[i]
            ny = y + move_y[i]

            if nx<0 or ny<0 or nx>=h or ny>=w :
              continue

            if graph[nx][ny] : 
              dfs( nx, ny )
              continue

    cnt = 0 

    for y in range(w):
      for x in range(h):
          if graph[x][y]:
            dfs(x,y)
            cnt += 1 
    return cnt 


p = []

while 1: 
    w, h = map(int,sys.stdin.readline().split()) # 지도 너비, 높이 <= 50 
    if w == 0 and h == 0 : 
        break 
    else:
        p.append( island(w,h) )

for i in range(len(p)):
  print(p[i])

 

거의 구현 문제다.. 

 

1. 섬과 바다 지도를 graph 에 받아오기 

2. 만약 내가 지금 방문한 노드가 섬이라면, 인접한 섬 방문하는 dfs 재귀 방법 사용 

   ( 인접한 섬을 방문하는 경우의 수는 가로 2개 세로 2개 대각선 4개하여, 총 8가지 이다. ) 

3. 한 번 탐색을 끝나면 섬 하나가 끝난 것이므로 cnt +1 

 

tip) 런타임 에러 해결 

-> 보토 입력값이 크고 파이썬은 조금 느린 언어다 보니까 입력하는 부분에서 런타임 에러가 발생할 수 있다. 

 

import sys

sys.setrecursionlimit(10000000)

w, h = map(int,sys.stdin.readline().split())

 

위의 코드를 통하여 해결한다. ( 모든 입력 부분에 sys.stdin.readline() 을 사용한다 )