🔡 Coding Test

[Algorithm] BFS(너비 우선 탐색)

💡 시작하기

이걸 갑자기 왜 뜬금없이 정리하냐면

코테 문제 풀 때 내가 제일 약한 게 트리랑 그래프다 트리가 특히 진짜 약하다.. 머리가 1도 안 돌아감.

그리고 맨날 DFS, BFS 언제 쓰는지도 모르고 어떻게 구현하는지도 까먹는다 ㅜ.ㅜ 친구한테 설명을 들어도 이해가 되기는 하는데 막상 구현하려면 그래서 어떻게 하는 건데..? 가 되어버림..

그래서 냅다 정리해보았다

🖥️ BFS 쓰는 이유 : 최단 경로 보장

왜 BFS는 최단 경로를 보장할까?

각 지점으로 갈 수 있는 모든 방향으로 뻗음 따라서 BFS는 각 지점의 단계별 탐색 깊이가 같으므로 도착 지점까지의 최단 거리를 찾을 수 있음

또한 각 과정마다 최선의 탐색을 하므로 이미 거쳐온 경로는 다시 탐색하지 않아도 됨

BFS에서 큐를 사용하는 이유

먼저 들어온 노드를 먼저 탐색하기 위해서이다(라고만 들었을 때 이해를 1도 못함)

BFS는 가까운 노드부터 차례대로 탐색하는 알고리즘인데, 이 순서를 보장해주는 자료구조가 바로 큐다!

시작점에서 출발
시작점과 인접한 노드를 모두 큐에 넣음
큐에서 하나씩 꺼내면서 탐색 진행

이 과정을 반복하면 자연스럽게 거리 1 → 거리 2 → 거리 3 … 순으로 탐색이 진행된다.

이로 인해 최단 경로가 보장되는 것도 자연스럽게 설명된다!!

🤔 문제 - 미로 탈출

코딩테스트 연습 - 미로 탈출 | 프로그래머스 스쿨

알고리즘 문제 연습 카카오톡 친구해요! 프로그래머스 교육 카카오 채널을 만들었어요. 여기를 눌러, 친구 추가를 해주세요. 신규 교육 과정 소식은 물론 다양한 이벤트 소식을 가장 먼저 알려드립니다.

school.programmers.co.kr

나는 프로그래머스에서 풀어봤다!

문제 설명

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

제한사항

5 ≤ maps의 길이 ≤ 100
- 5 ≤ maps[i]의 길이 ≤ 100
- maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
  - S : 시작 지점
  - E : 출구
  - L : 레버
  - O : 통로
  - X : 벽
- 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
- 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

입출력 예

maps	result
["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]	16
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]	-1

📖 진짜 어떻게든 이해하려고 적은 나만의 노트

코드를 짤 때는

시작점을 큐에서 shift()
상하좌우로 갈 수 있는 곳들은 모두
- visited ⇒ true
- queue에 push() → 넣을 때 shift했던 값의 dist + 1
도착지점 오면 거리 출력

🔡 코드

function bfs(maps, start, target) {
  const dx = [0, 0, -1, 1];
  const dy = [-1, 1, 0, 0];

  const col = maps.length;
  const row = maps[0].length;

  var queue = [];
  var visited = Array.from({ length: col }, () => Array(row).fill(false));

  queue.push([start[0], start[1], 0]);
  visited[start[0]][start[1]] = true;

  while (queue.length) {
    const [x, y, dist] = queue.shift();

    if (x === target[0] && y === target[1]) return dist;

    for (let i = 0; i < 4; i++) {
      const xpos = x + dx[i];
      const ypos = y + dy[i];

      if (
        xpos >= 0 &&
        xpos < col &&
        ypos >= 0 &&
        ypos < row &&
        !visited[xpos][ypos] &&
        maps[xpos][ypos] !== "X"
      ) {
        visited[xpos][ypos] = true;
        queue.push([xpos, ypos, dist + 1]);
      }
    }
  }
  return -1;
}

function solution(maps) {
  var start = [0, 0];
  var lever = [0, 0];
  var exit = [0, 0];

  for (let i = 0; i < maps.length; i++) {
    for (let j = 0; j < maps[i].length; j++) {
      let pos = maps[i][j];
      if (pos == "S") start = [i, j];
      if (pos == "L") lever = [i, j];
      if (pos == "E") exit = [i, j];
    }
  }

  const toLever = bfs(maps, start, lever);
  if (toLever === -1) return -1;

  const toExit = bfs(maps, lever, exit);
  if (toExit === -1) return -1;

  return toLever + toExit;
}

📝 정리

트리가 너무 약해서 걱정이다

dfs는 이미 이해한 상태인데 bfs는 대체 언제 사용하는지 어떻게 해서 최단경로가 나오는 지를 이해하지 못했는데 이렇게 이해해서 정말 다행이다…

다음부터 잊지 않도록 bfs에 대한 문제를 종종 풀어봐야겠다 😊

← Back ↑ Top