[Python] 백준 4963 섬의 개수

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

4963번: 섬의 개수

 

문제 해결

움직일 수 있는 방향이 동서남북 대각선까지 총 8가지이다.

한 점을 잡고 갈수 있는 끝까지 가면서 Land를 Sea로 바꾸는 작업을 한다.

더이상 갈 수 없으면 다음 Land점을 잡고 똑같은 일을 한다. 

이를 DFS로 코드를 만들 수 있다.

백준은 sys.setrecursionlimit()를 꼭 써야하는 것 같다.

CODE

import sys
input = sys.stdin.readline
sys.setrecursionlimit(5000)
def solve(row,col):
    global board
    board[row][col] = 0
    for i in range(len(move)):
        idx = move[i][0]
        idy = move[i][1]
        new_row = row+idx
        new_col = col + idy
        if 0<=new_row and new_row<h and 0<=new_col and new_col<w and board[new_row][new_col] == 1:
            solve(new_row, new_col)


while 1:
    w, h = map(int, input().split())
    if w==0 and h ==0:
        break
    board = [list(map(int, input().split())) for _ in range(h)]
    move = [(1,0), (0,1), (-1,0), (0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]
    cnt = 0
    for col in range(w):
        for row in range(h):
           if board[row][col] ==1:
            cnt +=1
            solve(row,col)
    print(cnt)