- 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.
스택 자료구조
- 먼저 들어온 데이터가 나중에 나가는 형식(선입후출,FILO)의 자료구조.
- 입구와 출구가 동일한 형태로 스택을 시각화한다.
stack = []
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()
print(stack[::-1]) # 최상단 원소부터 출력
print(stack) # 최하단 원소부터 출
#실행결과
[1, 3, 2, 5]
[5, 2, 3, 1]
큐 자료구조
- 먼저 들어온 데이터가 먼저 나가는 형식(선입선출, FIFO)의 자료구조.
- 입구(오른쪽)와 출구(왼쪽)가 모두 뻥 뚫린 상황으로 시각화.
- popleft(), pop()으로 명령어가 구성되어 있음.
from collections import deque
queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()
print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력
#실행결과
deque([3, 7, 1, 4])
deque([4, 1, 7, 3])
재귀 함수(Recursive Function)
- 자기 자신을 호출하는 함수.
- 재귀 함수의 종료 조건을 반드시 명시해야 한다. (무한 루프 방지)
factorial
def factorial_iterative(n): #반복문 이용
result = 1
for i in range(1,n+1):
result *= i
return result
def factorial_recursive(n): #재귀함수 이용
if n<=1:
return 1
return n*factorial_recursive(n-1)
print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))
#반복적으로 구현: 120
#재귀적으로 구현: 120
유클리드 호제법
def gcd(a,b):
if(b==0):
return a
else:
return gcd(b,a%b)
print(gcd(192, 162))
- 복잡한 알고리즘을 간결하게 작성할 수 있지만 다른 사람이 이해하기 어려운 형태의 코드가 될 수 있으므로 신중해야 한다.
DFS
- 깊이 우선 탐색
- 스택 자료구조(혹은 재귀 함수)를 이용
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
# 각 노드가 연결된 정보를 표현
# 0 : [] // 0번 인덱스는 사용하지 않음.
# 1 : [2,3,8] ...
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7],
]
def dfs(graph,v,visited):
# 현재 노드를 방문 처리
visited[v] = True
print(v, end = ' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if(visited[i] == False):
dfs(graph,i,visited)
visited = [False] * 9
dfs(graph,1,visited)
#실행 결과
1 2 7 6 8 3 4 5
BFS
- 너비 우선 탐색
- 큐 자료구조를 이용한다.
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
- 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
from collections import deque
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7],
]
def bfs(graph,start,visited):
# start 노드를 queue의 초기값으로 설정
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
visited = [False] * 9
bfs(graph,1,visited)
#실행결과
1 2 3 8 7 4 5 6
음료수 얼려 먹기 문제
- N x M 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시됩니다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주합니다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하세요. 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성됩니다.
===================================
4 5
00110
00011
11111
00000
===================================
DFS 공부 전 나의 접근
# 행렬형태의 입력 받기
m,n = map(int, input().split())
v=[]
for i in range(m):
line = input()
if len(line) == n :
number_list = [int(num) for num in line]
else :
print("입력값 오류")
break
v.append(number_list)
def dfs(blocks):
count = 0
for i in range(m):
for j in range(n):
c = v[i][j]
if(c==0):
v[i][j] = 1
count +=1
if i<=-1:
continue
else:
v[i-1][j] = 1
if i+1 >= m :
continue
else:
v[i+1][j] = 1
if j <= -1 :
continue
else:
v[i][j-1] = 1
if j+1 >= n :
continue
else:
v[i][j+1] = 1
dfs(v)
#결과
3
- 일단 DFS를 재귀 함수 형태로 사용하지 않았음. 이는 노드들의 연결이 없다는 것과 마찬가지임.
- continue로 인해서 위아래 값들의 변경이 이루어 지지않음.
DFS
# 행렬형태의 입력 받기
def dfs(x,y):
if(x <= -1 or x>=m or y <= -1 or y>=n ):
return False
else:
if graph[x][y] == 0 :
graph[x][y] = 1
dfs(x-1,y) # 위
dfs(x+1,y) # 아래
dfs(x,y+1) # 오른쪽
dfs(x,y-1) # 왼쪽
return True
return False
if __name__ == "__main__" :
m,n = map(int, input().split())
global graph
graph=[]
result = 0
for i in range(m):
line = input()
if len(line) == n :
number_list = [int(num) for num in line]
else :
print("입력값 오류")
exit()
graph.append(number_list)
for j in range(m):
for k in range(n):
if dfs(j,k) == True:
result += 1
print(result)
- 계산시 노드들의 연결을 재귀함수로 구현하는 것이 포인트.
BFS
from collections import deque
def bfs(x,y):
q = deque()
q.append((x,y))
if num_list[x][y] == 1:
return False
else:
if num_list[x][y] == 0:
while q :
x,y = q.popleft()
num_list[x][y] = 1
for _ in range(4):
mx = x+dx[_]
ny = y+dy[_]
if( -1 < mx < m and -1 < ny < n and num_list[mx][ny] == 0):
q.append((mx,ny))
return True
if __name__ == "__main__":
m,n = map(int, input().split())
global num_list
num_list = []
count = 0
for i in range(m):
nums = input()
num_set = [int(char) for char in nums]
num_list.append(num_set)
dx = [0,0,1,-1]
dy = [1,-1,0,0]
for j in range(m):
for k in range(n):
if(bfs(j,k)==True):
count+=1
print(count)
미로 탈출 문제
- 동빈이는 NxM 크기의 직사걱형 형태의 미로에 갇혔다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야한다.
- 동빈이의 위치는 (1,1)이며 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다.
- 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하세요. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산합니다.
===================================
5 6
101010
111111
000001
111111
111111
===================================
#결과 10
나의 풀이
from collections import deque
def bfs(x,y):
q = deque()
q.append((x,y))
count = 0
while q :
x,y = q.popleft()
if(num_list[x][y] == 1):
count += 1
if(x<n-1 and num_list[x+1][y] == 1) :
q.append((x+1,y))
if(y<m-1 and num_list[x][y+1] == 1) :
q.append((x,y+1))
return count
if __name__ == "__main__":
n,m = map(int,input().split())
global num_list
num_list = []
for i in range(n):
nums = input()
num_set = [int(char) for char in nums]
num_list.append(num_set)
print(bfs(0,0))
- 출발지와 도착지가 정해져 있기 때문에 오른쪽과 아래쪽으로 움직인 거리 만을 고려했다. 또한 거리를 계산할 때 노드 값을 업데이트 하는 것이 아니라 count 변수를 업데이트하였다.
해답
from collections import deque
def bfs(x,y):
q = deque()
q.append((x,y))
while q :
x,y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >=n or ny <0 or ny >= m:
continue
if graph[nx][ny] == 0 :
continue
if graph[nx][ny] == 1 :
graph[nx][ny] = graph[x][y] + 1
q.append((nx,ny))
return graph[n-1][m-1]
n,m = map(int,input().split())
graph = []
for i in range(n):
graph.append(list(map(int,input())))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
print(bfs(0,0))
