[Python] DFS/BFS_음료수 얼려 먹기

• 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조
  (오버플로우 : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입연산을 수행할 때 발생)
  (언더플로우 : 특정한 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태)

스택 : First In Last Out 구조 or Last In First Out 구조
큐 : First In First Out 구조
재귀함수 : 자기 자신을 다시 호출하는 함수

시간복잡도 : O(N)

• DFS : 깊이 우선 탐색, 멀리있는 노드부터 탐색하는 알고리즘
  스택을 이용하는 알고리즘(재귀함수 이용)
• BFS : 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘
  선입선출 방식인 큐 자료구조를 이용하는 알고리즘

def dfs(graph, v, visited):
	visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)
graph = [
   [], 
   [2, 3, 8], 
   [1, 7], 
   [1, 4, 5], 
   [3, 5], 
   [3, 4], 
   [7], 
   [2, 6, 8], 
   [1, 7]
]

visited = [false] * 9
dfs(graph, 1, visited)

def bfs(graph, start, visited):
	# 큐(Queue) 구현을 위해 deque 라이브러리 사용
	queue = deque([start])
    visited[start] = True
    while queue:
    	v = queue.popleft()
        print(v, end=' ')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True    
graph = [
   [], 
   [2, 3, 8], 
   [1, 7], 
   [1, 4, 5], 
   [3, 5], 
   [3, 4], 
   [7], 
   [2, 6, 8], 
   [1, 7]
]

visited = [false] * 9
bfs(graph, 1, visited)

음료수 얼려 먹기

문제

N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.
다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다

입력

첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.
출력
한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

입력 예시 1

4 5
00110
00011
11111
00000

출력 예시 1

3

입력 예시 2

15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111

출력 예시2

8

풀이

n, m = map(int, input().split())

graph = []
for i in range(n):
	graph.append(list(map(int, input())))
    
def dfs(x, y):
	if x <= -1 or x >= n or y <= -1 or y >= m:
    	return False
    if graph[x][y] == 0:
    	graph[x][y] = 1
        # 상, 하, 좌, 우의 위치도 모두 재귀적으로 호출
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False
    
result = 0
for i in range(n):
	for j in range(m):
    	if dfs(i, j) == True:
        	result += 1
print(result)