[DFS][백준, 4963] 섬의 개수

문제 풀이

1. 이중 반복문을 통해서 최초 land를 찾는다.

 (1) 최초로 발견되는 land의 개수를 카운트 한다.

 (2) 2번 과정을 수행한다.

 

2. 최초 land의 좌표부터 깊이 우선탐색(DFS)을 수행한다.

 (1) 탐색된 land(1)를 sea(0)으로 바꾼다.

 

3. 정답을 리턴한다.

 

코드

import sys

# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def dfs(x, y):
    board[y][x] = 0
    for i in range(8):
        next_x = x + dx[i]
        next_y = y + dy[i]
        if 0 <= next_x < w and 0 <= next_y < h and board[next_y][next_x] == 1:
            dfs(next_x, next_y)


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

if __name__ == '__main__':
    # 8방향 탐색
    dx = [0, 0, 1, -1, -1, -1, 1, 1]
    dy = [-1, 1, 0, 0, -1, 1, -1, 1]

    while True:
        # 데이터 입력
        w, h = map(int, sys.stdin.readline().split())  # w: 너비(x), h: 높이(y)
        if w == 0 and h == 0:
            break
        board = [list(map(int, sys.stdin.readline().split())) for _ in range(h)]

        # 섬 탐색
        ans = calc_num_land()
        print(ans)