탐색
개념
탐색이란 많은 양의 테이터 중에서 원하는 데이터를 찾는 과정
스택(FILO)
개념
먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
파이썬에서
파이썬에서는 list의 pop() 메서드를 지원한다. 그래서 pop() 메서드를 통해 리스트를 마치 스택처럼 사용 가능하다.
큐(FIFO)
개념
먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
파이썬에서
from collections import deque
queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.popleft()코드와 같이 queue를 정의하고 삽입, 삭제가 가능하다.
재귀함수(Recursive Function)
개념
자기 자신을 다시 호출하는 함수
예시
1.
def factorial_recursive(n):
if n <= 1:
return 1
return n * factorial_recursive(n-1)위와 같이 팩토리얼을 재귀함수로 구현 가능하다.
2.
최대공약수를 구할 때 유클리드 호제법을 이용해서 구할 수 있다. 이것을 재귀함수로 나타내면
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)DFS
개념
깊이 우선 탐색이라고 불리며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
동작 과정
-
탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
-
스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
-
더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.
예제
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
def dfs(graph, v, visitied):
visitied[v] = True
print(v, end=' ')
for i in graph[v]:
if not visitied[i]:
dfs(graph, i, visitied)
visited = [False] * 9
dfs(graph, 1, visited)재귀함수를 통해서 dfs를 구현할 수 있다. 먼저 그래프를 위와 같이 정의하고, 그래프가 오름차순으로 정의되어 있기 때문에 각 상황에서 숫자가 낮은 순서부터 탐색을 진행한다.
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, visitied):
queue = deque([start])
visitied[start] = True
while queue:
v = queue.popleft()
print(v, end=' ')
for i in graph[v]:
if visitied[i] == False:
visitied[i] = True
queue.append(i)
visited = [False] * 9
bfs(graph, 1, visited)BFS의 경우 큐를 활용 해야한다. 먼저 큐에 1의 인접한 노드들을 순서대로 넣는다. 그리고 pop을 하면서 다음 노드의 인접 노드를 큐에 넣는다. 이 로직을 반복하면 인접 노드를 우선 탐색할 수 있다.
DFS & BFS 예제
1.
💡아이디어
영상에서는 DFS를 이용해서 풀었지만 나는 BFS를 이용해서 풀었다.
2차원 공간이기 때문에 먼저 2차원 리스트를 만들고, 방향 벡터를 만들어 인접한 노드들을 차례로 탐색하는 방법을 떠올렸다.
from collections import deque
dColumn = [1, -1, 0, 0]
dRow = [0, 0, 1, -1]
row, column = map(int, input('입력 = ').split())
array = [[0] * column for _ in range(row)]
visited = [[False] * column for _ in range(row)]
for i in range(row):
s = input('')
for j in range(len(s)):
if s[j] == '1':
array[i][j] = 1
result = 0
for i in range(row): # 로직 시작
for j in range(column):
if array[i][j] == 0 and visited[i][j] == False:
queue = deque([(i, j)])
visited[i][j] = True
while queue:
pop = queue.popleft()
for k in range(4):
movedRow = pop[0] + dRow[k]
movedColumn = pop[1] + dColumn[k]
if movedRow >= row or movedRow < 0 or movedColumn >= column or movedColumn < 0:
continue
if array[movedRow][movedColumn] == 0 and visited[movedRow][movedColumn] == False:
visited[movedRow][movedColumn] = True
queue.append((movedRow, movedColumn))
result += 1
print(result)먼저 방향 벡터, 2차원 얼음판, visited를 정의한다.
로직이 시작하는 부분을 보자. 먼저 2중 for문을 통해서 모든 노드를 탐색한다. 만약 탐색하는 노드가 0이고 방문하지 않았다면 큐에 넣고, visited = True로 바꾼다. 그 후에 큐가 끝날 때까지 while문을 돌린다.
while문에서는 큐에 담긴 노드를 꺼내어 동서남북으로 이동해본다. 범위를 넘지않은 노드에서 0이면서 방문하지 않았다면 큐에 넣는다. 만약 인접한 모든 노드를 방문해서 큐에 노드가 없으면, 하나의 아이스크림이 만들어진 것이니까 result += 1을 한다. 그리고 다음 탐색하지 않은 노드를 찾아 로직을 반복한다.
2.
💡아이디어
이 문제를 처음 풀이로 도전 했을 때는 재귀함수를 활용한 DFS로 시도했다. 하지만 '최소한'의 움직임이라는 것을 재귀함수 DFS로 풀기에는 로직이 너무 복잡해져서 실패했다...
결국 다음 아이디어가 생각나지 않아서 BFS로 진행하는 힌트를 얻고 다시 풀어보았다.
from collections import deque
dColumn = [1, -1, 0, 0]
dRow = [0, 0, 1, -1]
row, column = map(int, input('입력 = ').split())
array = [[0] * column for _ in range(row)]
value = [[0] * column for _ in range(row)]
for i in range(row):
s = input('')
for j in range(len(s)):
if s[j] == '1':
array[i][j] = 1
def bfs(array, v):
value[v[0]][v[1]] = 1
queue = deque()
queue.append((v[0], v[1]))
while queue:
pop = queue.popleft()
for i in range(len(dRow)):
movedRow = pop[0] + dRow[i]
movedColumn = pop[1] + dColumn[i]
if movedRow >= row or movedRow < 0 or movedColumn >= column or movedColumn < 0:
continue
if array[movedRow][movedColumn] == 1 and value[movedRow][movedColumn] == 0:
queue.append((movedRow, movedColumn))
value[movedRow][movedColumn] = value[pop[0]][pop[1]] + 1
for i in value:
print(i)
return value[row - 1][column - 1]
print(bfs(array, (0, 0)))이번 문제도 저번 문제와 변수 정의를 비슷하게 했지만 visited대신 value를 넣었다. value를 통해서 해당 좌표까지의 최소한의 움직임을 저장하도록 했다.
(0,0)부터 시작해서 큐에 있는 값을 가져와 해당 좌표에서 동서남북으로 움직일 수 있는 방향 중에 방문하지 않은 좌표에 value값을 현재 좌표까지 이동한 값에 + 1을 해주어 넣어준다.
이렇게 로직을 반복하면 value에 각 좌표에 접근할 때 가장 최소한의 움직임의 맵이 만들어진다.
