-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
문제 접근법
23.12.18 00:39 작성 조회수 147
0
안녕하세요 강사님.
문제를 보고 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)
답변을 작성해보세요.
답변 1