• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

코드 검토

24.01.24 16:41 작성 조회수 95

0

안녕하세요! 선생님의 bfs 풀이 아이디어를 듣고 혼자 풀어봤습니다! 저의 경우 ch 랑 dis를 합쳐서 check 로 풀어서, 디폴트가null 이어서 널 이면 큐에 넣고, 숫자가 들ㄹ어가있으면 continue 하는 식을로 했는데 괜찮을까요?

function solution(s, e) {
  let answer = 0;
  let dx = [1, -1, 5];
  let check = Array.from({ length: 10001 }, () => null);
  check[s] = 0;
  let queue = [];
  queue.push(s);

  while (queue.length) {
    let v = queue.shift();
    if (v === e) {
      answer = check[v];
      break;
    }
    for (let a of dx) {
      let x = a + v;
      if (check[x] !== null || x < 1 || x > 10000) continue;
      check[x] = check[v] + 1;
      queue.push(x);
    }
  }
  return answer;
}

 

답변 1

답변을 작성해보세요.

0

인프런 AI 인턴님의 프로필

인프런 AI 인턴

2024.01.26

안녕하세요, 인프런 AI 인턴입니다.
00님, BFS 문제풀이 시도에 대하여 질문해 주셨군요.

네, 00님께서 작성하신 코드에서 chdis 배열을 하나의 check 배열로 합쳐 null 값을 초기 상태로 두고, 방문 여부 및 거리를 기록하는 방식은 올바른 접근입니다. 각 위치에 처음 방문하는 경우에만 큐에 넣어 BFS를 진행하고, 이미 방문했던 위치거나 범위를 벗어난 경우 다음 노드로 넘어가는 로직으로 잘 작성하셨습니다.

위 코드는 BFS를 이용하여 최단 거리를 찾는 문제에서 자주 사용하는 패턴인데요, 그대로 사용하셔도 무방합니다. 하지만 실제 문제가 어떤 범위의 값과 어떤 조건을 가지고 있는지에 따라 코드를 적절하게 수정할 필요는 있을 수 있습니다.

정리하면, null 값으로 초기화하고 방문하지 않았음을 표시한 뒤, 방문 시 해당 단계의 거리를 기록하는 방식은 BFS를 통해 최단 경로를 찾는 문제에 적합한 전략입니다.

계속해서 좋은 문제 해결 방법을 찾아나가시길 바랍니다. 화이팅입니다!