탐색 시작 노드를 스택에 삽입하고 방문처리한다
스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리함. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
더이상 2번의 과정을 수행할 수 없을때까지 반복
깊이우선 탐색
깊은 부분을 우선적으로 탐색하는 알고리즘
스택 자료구조 혹은 재귀함수를 이용한다.
탐색 시작 노드를 스택에 삽입하고 방문처리한다
스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리함. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
더이상 2번의 과정을 수행할 수 없을때까지 반복
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False] * 9
def dfs(graph, v, visited):
visited[v] = True
print(v,end=' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i , visited)
dfs(graph,1, visited)
넓이우선탐색. 가까운 노드부터 우선적으로 탐색하는 알고리즘
큐 자료구조를 사용한다.
탐색 시작 노드를 큐에 삽입하고 방문처리
큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 큐에 삽입하고 방문처리
더 이상 2번의 과정을 수행할 수 없을때까지 반복
from collections import deque
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False] * 9
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
# until queue is empty
while queue:
v = queue.popleft()
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
bfs(graph, 1, visited)
N*M크기의 얼음 틀이 있다. 구멍이 뚫려있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려있는 부분끼리 상하좌우로 붙어있는 경우 서로 연결되어있는 것으로 간주한다. 얼음 틀의 모양이 주어졌을때 생성되는 총 아이스크림 개수를 구해라.
<aside> 💡
map(int, ...)map()은 두 개의 인자를 받는 함수입니다: 첫 번째 인자는 변환할 함수, 두 번째 인자는 변환할 iterable(반복 가능한 객체)입니다.int는 문자열을 정수로 변환하는 함수입니다.map(int, ['1', '2', '3', '4'])는 ['1', '2', '3', '4']의 각 요소를 int로 변환하여 [1, 2, 3, 4]를 생성합니다.map()은 변환된 값을 반환하는 map 객체를 생성하므로, 이를 list()로 감싸야 리스트로 변환할 수 있습니다.
</aside>n,m = map(int, input().split())
# N*M 2차원 배열 입력받기
graph = []
for i in range(n):
graph.append(list(map(int,input())))
result = 0
def dfs(x,y):
if x < 0 or x>=n or y<0 or y>=m:
return False
else:
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
else:
return False
for i in range(n):
for j in range(m):
if dfs(i,j) == True:
# 연결된 모든 노드들은 이미 1로 바뀌어있기때문에 중복 count가 발생하지 않음
result+=1
print(result)
0인 노드를 찾고, DFS를 통해서 해당 노드와 인접한 모든 0인 노드를 찾아서 방문처리함.