1. 깊이 우선 탐색(Depth First Search)

• 최대한 깊숙하게 들어가서 확인 후, 다시 돌아가 다른 경로로 탐색하는 방식
• 구현 : 재귀함수
• 체크인, 체크아웃은 반드시 같은 depth에 존재해야 한다.

1. 체크인 (재방문방지)
2. 목적지인가?
3. 연결된 곳을 순회(가지치기)
		4. 갈수있는가?
				5. 간다.
6. 체크아웃

1-1) 백트래킹

: 재귀를 이용한 완전 탐색 기법

• 가지치기를 이용하여 탐색을 시도하다가 유망하지 않으면 ⇒ 노드를 제외하고 탐색을 진행한다.
• DP를 함께 이용한다.

Algorithm/Boj9202_Boggle.java at master · Jionee/Algorithm

static void dfs(int row, int col, int length, TrieNode node){
  //1. 체크인 -> visit = true
  **visit[row][col] = true;
  sb.append(map[row][col]);
  System.out.println("----> CheckIn "+sb.toString());**

  //2. 목적지인가? -> Trie.search가 true이면 목적지 && isHit == false
  // -> isHit = true 바꾸기, 점수 갱신, count 갱신, 가장 긴 단어 갱신
  if(trie.search(sb.toString()) && node.isHit == false){
      node.isHit = true;
      sum += score[length];
      count++;
      if(compare(longest,sb.toString()) > 0){
          longest = sb.toString();
      }
  }
  //3. 인접한 곳 순회
  for(int i=0;i<8;i++){//왼,오,위,아래,대각선왼쪽위,대각선오른쪽위,대각선왼쪽아래,대각선오른쪽아래
      int nextRow = row + mRow[i];
      int nextCol = col + mCol[i];
      //4. 갈수있는가? -> 벽 안됨, visit==false만, 자식이 있으면
      if(0 <= nextRow && nextRow < 4 && 0<= nextCol && nextCol < 4){
          if(visit[nextRow][nextCol] == false && node.hasChild(map[nextRow][nextCol])){
              //5. 간다 dfs
              dfs(nextRow,nextCol,length+1,node.getChild(map[nextRow][nextCol]));
          }
      }
  }

  **// 6. 체크아웃 -> visit = false
  visit[row][col] = false;
  sb.deleteCharAt(length-1);
  System.out.println("CheckOut ----->"+sb.toString());**
}

2. 너비 우선 탐색(Breadth First Search)

• 인접한 노드를 먼저 탐색하는 방식
• 구현 : Queue
• bfs로만 풀 수 있는 문제가 있다.
  • 동시에 여러개를 함께 움직여야 하는 경우
  • 상황이 계속해서 변하는 경우

0. 시작점 큐에 넣기
1. 큐에서 꺼내옴
2. 목적지인가?
3. 연결된 곳을 순회(가지치기)
		4. 갈수있는가?
		5. 체크인
		6. 큐에 넣음
(7.체크아웃)

 static Queue<T> queue = new LinkedList<>();

 * 0. 큐에 시작점 넣기
 *          while(!queue.isEmpty()){
 *             1. 큐에서 가져옴 -> S, ., D, *
 *             2. 목적지인가? -> D
 *             3. 연결된 곳을 순회 -> 좌,우,위,아래
 *                 4. 갈 수 있는가?(고슴도치) -> 맵을 벗어나지 않음, . or D, 방문하지 않음
 *                     5. 체크인 -> dp에 현재 +1 기록
 *                     6. 큐에 넣음
 *                 4. 갈 수 있는가?(물) -> 맵을 벗어나지 않음, .
 *                     5. 체크인 -> 지도에 * 표시
 *                     6. 큐에 넣음
 *         }
    

3. 정렬

• 리스트 정렬