인프런 커뮤니티 질문&답변

안녕하세요 강사님.

문제를 보고 dfs 구현이 더 맞다고 생각하여 다음과 같이 dfs 방식으로 접근해서 해결했는데, bfs 방식으로 푸는 것이 더 옳바른 방향인가요? 복잡도 등의 측면에서 강사님의 풀이가 더 좋을까요?

import sys
sys.stdin = open('in5.txt','r')

def dfs(y,x):
    global cnt
    # 현재 섬 방문 표시 후
    # 주변에 섬 더 있는지 탐색
    arr[y][x] = 0
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=ny<=(N-1) and 0<=nx<=(N-1) and arr[ny][nx] == 1:
            dfs(ny,nx)

if __name__ == '__main__':
    # 입력정보 저장하기
    N = int(input()) # 격자판 크기
    arr = [list(map(int,input().split())) for _ in range(N)] # 맵 정보

    # 상하좌우대각선 탐색 변수
    dx = [0,1,0,-1,-1,1,1,-1]
    dy = [-1,0,1,0,-1,-1,1,1]

    cnt = 0 # 섬 갯수 저장

    # 맵 전부 탐색
    for i in range(N):
        for j in range(N):
            # 만약 섬이 발견되면 dfs로 넘겨주기
            if arr[i][j] == 1:
                dfs(i,j)
                cnt += 1

    print(cnt)