전형적인 DFS 문제였다
여기로 갔다가 어떻게 돌아오지? 라는 생각이 들면
무조건 재귀를 떠올릴 것
너무 시간을 많이 까먹는게 아니라면 시간복잡도에 걸릴 일도 없고
효율적으로 탐색할 수 있다
import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
INF = int(1e9)
def dfs(graph,row,col,N,M):
if row < 0 or row >= N or col < 0 or col >= M:
return False
if graph[row][col] == 0:
graph[row][col] = 1
dfs(graph,row+1,col,N,M)
dfs(graph,row,col+1,N,M)
dfs(graph,row-1,col,N,M)
dfs(graph,row,col-1,N,M)
return False
N,M = map(int,sys.stdin.readline().split())
graph =[]
for i in range(N):
graph.append(list(map(int,sys.stdin.readline().rstrip())))
count = 0
for i in range(N):
for j in range(M):
if graph[i][j] == 0:
dfs(graph,i,j,N,M)
count +=1
print(count)
피드백 할거는
N,M을 위에 입력받고
함수를 아래부분에 썼으면 함수 인자가 복잡해지지 않았을 것
하여튼 요약
DFS : 스택 이용, Deep하게 깊이 우선 탐색 / 재귀 방식 이용
BFS: 큐 이용 (파이썬은 queue = deque()가 일반적) , 너비 우선 탐색, 재귀 방식 아니라서 마음에 든다.
'알고리즘 문제 풀이 > 이코테' 카테고리의 다른 글
[이코테] CH03 그리디 실전문제 큰수의법칙 (1) | 2023.11.13 |
---|---|
[이코테] DFS/ BFS 실전문제 4 미로 탈출 (0) | 2023.11.04 |
[이코테 Python] 구현 실전문제 3 게임 개발 (0) | 2023.10.03 |
Chapter 4.구현 / 실전 문제 왕실의 나이트 (0) | 2023.09.29 |
[이코테] 최단경로 문제 3 [전보] 파이썬 풀이 (0) | 2023.07.19 |