지뢰찾기 구현 과정에서 적용한 DFS 알고리즘(feat. BFS 알고리즘)

채용 전형 과제로 진행하던 지뢰찾기 게임 만들기에서
특정 셀을 클릭했을때, 여러개가 열리게 하는 기능을 찾던 중에
DFS 알고리즘을 적용하게 되어 나중에도 이렇게 적용할 수 있다는 걸 기억하기 위해 기록해둔다.

우선 DFS 알고리즘이란 무엇인가?
그리고 피쳐링으로 항상 짝꿍처럼 같이 나오는 BFS 알고리즘도 한번 복습겸 정리해 보기로!

DFS (Depth First Search)

aka 깊이 우선 탐색
스택(선입후출 형식)자료구조나 재귀로 구현이 가능하다 (재귀함수를 스택처럼 활용할 수 있다)

• 시작 노드를 스택에 삽입하고 방문처리
• 현재 노드와 연결된 다른 노드를 재귀적으로 방문해, 방문하지 않은 경우 함수를 다시 호출
  ---> 이 방식을 지뢰찾기에 적용했다.

아래 예시는 스택활용한 코드

   dfs(idx) {
    let root = this.nodes[idx]; //idx를 받아 nodes 배열에서 루트노드를 정함
    let stack = []; // 스택 생성
    stack.push(root); // 스택에 루트 노드 푸시
    root.visited = true; // 루트 노드 스택에 들어갔으니 방문 체크

    while (stack.length !== 0) { // 스택이 비어있을 때 까지
      let popedNode = stack.pop(); // 스택에서 노드 하나 꺼냄

      for (let adjacencyNode of popedNode.adjacencyList) { // 꺼낸 노드의 인접 노드들
        if (adjacencyNode.visited === false) { // 인접노드에 방문 안했으면
          adjacencyNode.visited = true; // 방문처리
          stack.push(adjacencyNode); // 스택에 해당 인접노드 푸시
        } // 스택에는 루트의 인접노드들이 쌓이고 인접노드들이 또 쌓이고 반복하다가
      } //  인접노드가 없으면 반복문이 종료되고 종료 되고 종료되고 반복하다가
      this.visit(popedNode);
    } //  stack의 모든 노드들을 방문하면 dfs 함수 최종 종료
  }

BFS (Breadth First Search)

aka 너비 우선 탐색
큐(선입선출)자료구조로 구현이 가능하다

• 시작 노드를 큐에 삽입하고 방문처리
• 큐에서 노드를 꺼내고, 꺼낸 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
• 이를 수행할 수 없을때까지 반복

예시

  bfs(idx) {
    let root = this.nodes[idx];
    let queue = []; // 큐 생성
    queue.push(root); // 큐에 루트 노드 푸시
    root.visited = true; // 방문 처리
					// 이하 dfs스택과 설명 동일
 
    while (queue.length !== 0) {
      let deQueuedNode = queue.shift();

      for (let adjacencyNode of deQueuedNode.adjacencyList) {
        if (adjacencyNode.visited === false) {
          deQueuedNode.visited = true;
          queue.push(adjacencyNode);
        }
      }
      this.visit(deQueuedNode);
    }
  }

참고 블로그

이렇게 복습을 완료
두 알고리즘은 queue 와 stack의 차이가 있다고 이해하면 될 것 같다.
코딩테스트 연습할 때도 종종 나오는 거라
전체적인 흐름을 제대로 이해하고 있어야 할 것 같다.
어떤 방식을 어떤 문제에 적용해야 할 지도...!

내 지뢰찾기 리듀서에 적용한 일부 코드를 적어보자면(재귀로 구현)

// 주변 인접한 셀
const getNeighbors = (row: number, col: number, rows: number, cols: number) => {
  const neighbors: CellPosition[] = [];

  // Check top neighbor
  if (row - 1 >= 0) {
    neighbors.push({ row: row - 1, col });
  }
  // Check bottom neighbor
  if (row + 1 < rows) {
    neighbors.push({ row: row + 1, col });
  }
  // Check left neighbor
  if (col - 1 >= 0) {
    neighbors.push({ row, col: col - 1 });
  }
  // Check right neighbor
  if (col + 1 < cols) {
    neighbors.push({ row, col: col + 1 });
  }
  // Check top-left neighbor
  if (row - 1 >= 0 && col - 1 >= 0) {
    neighbors.push({ row: row - 1, col: col - 1 });
  }
  // Check top-right neighbor
  if (row - 1 >= 0 && col + 1 < cols) {
    neighbors.push({ row: row - 1, col: col + 1 });
  }
  // Check bottom-left neighbor
  if (row + 1 < rows && col - 1 >= 0) {
    neighbors.push({ row: row + 1, col: col - 1 });
  }
  // Check bottom-right neighbor
  if (row + 1 < rows && col + 1 < cols) {
    neighbors.push({ row: row + 1, col: col + 1 });
  }

  return neighbors;
};

const expandOpenedCell = (
  board: CellState[][],
  row: number,
  col: number
): void => {
  // 지뢰 카운트를 위한 정의
  const getMineCount = (row: number, col: number): number => {
    const neighbors = getNeighbors(row, col, board.length, board[0].length);
    return neighbors.filter(
      ({ row: neighborRow, col: neighborCol }) =>
        board[neighborRow][neighborCol].isMine
    ).length;
  };

  // 연쇄클릭을 위한 DFS알고리즘 적용
  const dfsSearch = (row: number, col: number): void => {
    const cell = board[row][col];

    // 열려있거나, 깃발이 꽂혀있으면 동작 중단하고 함수종료
    if (cell.isOpen || cell.isFlagged) {
      return;
    }

    //셀을 열고, 해당 위치에 있는 지뢰개수를 계산해 저장
    cell.isOpen = true;
    cell.minesAround = getMineCount(row, col);

    // 주변에 지뢰가 없다면, 주변 셀들에 대해 재귀적으로 dfsSearch 함수를 호출해서 연쇄적으로 열리게 함
    if (cell.minesAround === 0) {
      const neighbors = getNeighbors(row, col, board.length, board[0].length);
      neighbors.forEach(({ row: neighborRow, col: neighborCol }) => {
        dfsSearch(neighborRow, neighborCol);
      });
    }
  };
  
// 호출
  dfsSearch(row, col);
};

이렇게 실제 앱을 구현하는 데에 있어서 알고리즘을 적용한다는 게
뭔가 새롭게 다가와서 블로그로 정리해봤다.
지뢰찾기의 경우에는 이것저것 참고할 다른 분들의 코드가 있어서
흐름을 잡기에 편했다.
확실히 앱을 구현할 때, 백지로 처음 시작부터 뼈대를 잡고 시작하는게 가장 어려운 것 같다.