알고리즘 문제 풀이/이코테
[이코테] CH05 DFS/BFS 실전문제 3번 음료수 얼려 먹기
파란색 가운
2023. 11. 27. 21:05
import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
INF = 1e9
def DFS(x,y):
while True:
if x >=N or y>=M or x<0 or y<0:
return False
if graph[x][y] == 0:
graph[x][y] = 1
DFS(x+1,y)
DFS(x,y+1)
DFS(x,y-1)
DFS(x-1,y)
return True
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 DFS(i,j) == True:
count +=1
print(count)
상하좌우에 대해서 DFS를 돌려준다
모든 칸에 대해서 DFS를 돌려보고 return값이 True가 나온다는 것은(상하좌우 탐색할 노드가 없는 경우)
빙하를 만들었다는 의미이므로 count +=1