[Backjoon] 섬의 개수

백준 4963번 섬의 개수 문제는 전형적인 그래프 탐색 문제이다. BFS, DFS 두 방법 모두 풀이가 가능하고 인접 행렬 형태의 자료구조를 탐색하는 연습을 하기에 좋은 문제이다. 문제를 풀면서 BFS로 접근했지만 메모리 초과, 시간 초과 문제로 DFS로 변경해서 풀이했다. 소스구조에 어떤 문제가 있는지는 차후에 분석해봐야 한다. 아래의 소스코드는 DFS로 풀이한 솔루션이다.

 

import sys
sys.setrecursionlimit(10**6)

def dfs(row, col):
    dx = [0, 0, 1, -1, 1, -1, 1, -1]
    dy = [1, -1, 0, 0, -1, 1, 1, -1]

    board[row][col] = 0

    for idx in range(8):
        nx = col + dx[idx]
        ny = row + dy[idx]

        if 0 <= nx < len(board[0]) and 0 <= ny < len(board) and board[ny][nx] == 1:
            dfs(ny, nx)

while True:
    col_count, row_count = list(map(int, sys.stdin.readline().split(" ")))

    if col_count == 0 and row_count == 0:
        break

    board = []
    for _ in range(row_count):
        board.append(list(map(int, sys.stdin.readline().split(" "))))

    count = 0
    for row in range(row_count):
        for col in range(col_count):
            if board[row][col] != 0:
                dfs(row, col)
                count += 1

    print(count)