Algorithm

[이코테] Chapter 05. DFS/BFS 학습 정리

꼭 필요한 자료구조 기초

💡 KEY POINT
탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조
스택: 선입후출/후입선출 구조
: 선입선출 구조
재귀 함수: 자기자신을 다시 호출하는 함수, 수학의 점화식을 그대로 소스코드로 옮겨놓음

 

탐색 알고리즘 DFS/BFS

💡 KEY POINT
그래프: 노드(정점)와 간선으로 표현되며, 인접 행렬과 인접 리스트 2가지의 방식으로 표현할 수 있다.
    - 인접 행렬 방식: 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비
    - 인접 리스트 방식: 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장하는 방식연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용하지만 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림

DFS: 깊이 우선 탐색, 깊은 부분을 우선적으로 탐색하는 알고리즘, 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘
BFS: 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘
  DFS BFS
동작 원리 스택
구현 방법 재귀 함수 이용 큐 자료구조 이용

 

[실전 문제] 음료수 얼려 먹기

💡 KEY POINT
DFS를 사용해서 풀이한다.
입력받은 얼음 틀을 N * M만큼 반복하여 방문하면서 먼저 해당 (i, j)의 주위에 있는 노드가 범위 내인지 확인한다. 이후 범위 내라면 DFS로 주변의 노드를 확인하고 방문되어있지 않다면 방문처리를 한다. DFS가 확인이 끝나면 다음 (i, j)로 넘어가 또 다시 DFS로 방문되어있는지 판단한다.

 

[실전 문제] 미로 탈출

💡 KEY POINT
BFS를 사용해서 풀이한다.
입력받은 미로에서 1인 경우가 갈 수 있는 길이므로, 갈 수 있으면서 아직 방문하지 않은 상태는 1이다.
이를 이용하여 갈 수 있는 위치를 1씩 더해 다시 저장한 값이 그 위치까지 갈 수 있는 최소거리이다.