글 읽기 - 아무리 생각해도 예외 케이스가 떠오르지 않습니다 ㅠ 도와주세요!

maxmp3105 1년 전 0

안녕하세요. 🙇‍♂️

제가 생각한 방식에서 예외 케이스가 도저히 안 떠오르는데, 자꾸 실패하여 질문드립니다 ㅠㅜ

현재 위치에서 다음 위치로 이동했을 때, 아래의 경우를 만족하는 경우만 enqueue 했습니다.

1. 이동 후의 위치에 사다리 또는 뱀이 있는 경우 & 방문한 적 없음 & 100 이하

2. 이동 후의 위치에 사다리 또는 뱀은 없지만 +6만큼 이동한 경우 & 방문한 적 없음 & 100 이하

이동할 수 있는 위치 중에 사다리 또는 뱀이 없다면, 다음 사다리 또는 뱀으로 가기 위해 최대한 많이 이동해야하므로 +6을 택해야 한다고 생각해서 위와 같이 코드를 짰는데, 혹시 예외 케이스가 있을까요?

긴 글 읽어주셔서 감사합니다!

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const [[n, m], ...input] = require('fs')
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((v) => v.split(' ').map(Number));

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  enqueue(val) {
    const newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.head.next = newNode;
      this.head = newNode;
    }
    this.size++;
  }

  dequeue() {
    if (this.size === 0) {
      return null;
    } else {
      const returnNode = this.tail;
      if (this.size === 1) {
        this.head = null;
        this.tail = null;
      } else {
        this.tail = returnNode.next;
      }
      this.size--;
      return returnNode;
    }
  }
}

const obj = { 100: true };
input.forEach((el) => {
  const [start, end] = el;
  obj[start] = end;
});

const visited = new Array(100).fill(false);
visited[0] = true;

// bfs
const queue = new Queue();
queue.enqueue([1, 0]);
let answer = 0;
while (queue.size) {
  let [curPos, level] = queue.dequeue().val;
  if (curPos === 100) {
    answer = level;
    break;
  } else if (obj[curPos]) {
    curPos = obj[curPos];
  }
  [1, 2, 3, 4, 5, 6].forEach((increment) => {
    // 이동할 위치에 사다리 또는 뱀이 있거나 범위 내에 있는 경우
    const newPos = curPos + increment;
    if ((obj[newPos] || increment === 6) && newPos <= 100 && !visited[newPos]) {
      queue.enqueue([newPos, level + 1]);
      visited[newPos] = true;
    }
  });
}

console.log(answer);

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

아무리 생각해도 예외 케이스가 떠오르지 않습니다 ㅠ 도와주세요!

maxmp3105 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말