🙂TIL from lecture

---

DFS(Depth-First Search)

깊이 우선 탐색 → 깊은 부분을 우선적으로 탐색한다

DFS는 스택 자료구조(혹은 재귀함수)를 이용한다.

1. 탐색 시작노드를 스택에 삽입, 방문처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문처리
3. 방문하지 않은 인접 노드가 없다면, 스택에서 최상단 노드를 꺼냄
4. 더 이상 2~3번의 과정을 수행할 수 없을 때까지 반복

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차원 리스트로 표현 (노드의 연결 정보)
# visited는 1차원 리스트로 표현 (노드의 방문 여부)

BFS(Breadth-First Search)

너비 우선 탐색 → 가까운 노드부터 우선적으로 탐색

BFS는 큐 자료구조를 이용한다.

1. 탐색 시작 노드를 큐에 삽입하고, 방문처리
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

from collections import deque

def bfs(graph, start, visited):
	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 #방문처리
	

🏆Today Code Test

---

🛠Problem Approach

문제

NxM 크기의 어름틀이 있다. 구멍이 뚫려있는 부분은 0, 칸막이가 존재하는 부분은 1이다.

구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다..

이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하세요

🔑Solution

n, m = map(int, input().split())
icemap = [input() for i in range(n)]
icemap = [[int(i[j]) for j in range(m)] for i in icemap]
# visit = [True  if i[j] == 1 else False for i in icemap for j in range(m)]

def search(map, x, y):
  dx = [1,-1, 0, 0]
  dy = [0, 0, 1, -1]
  if x >= n or x < 0 or y < 0 or y >= m: # index 확인
    return False
  if map[x][y] == 0:
    map[x][y] = 1
    for i in range(4): #동서남북 접근
      search(map, x+dx[i], y+dy[i])
    return True
  return False

cnt = 0
# 모든 map 탐색
for i in range(n):
  for j in range(m):
    if search(icemap, i, j):
      cnt += 1
print(cnt)