백준/ Gold 5 문제 , 백준 Node.js 자바스크립트 9205 맥주 마시면서 걸어가기 [ BFS, 그래프 이론 ]

백준/ Gold 5 문제 , 백준 Node.js 자바스크립트 9205 맥주 마시면서 걸어가기 [ BFS, 그래프 이론 ]

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

🏡 문제출처 

 

https://www.acmicpc.net/problem/9205

9205번: 맥주 마시면서 걸어가기

 

 

 

🏡 풀이소감

접근방식에서는 크게 틀린 것이 없었는데 계속 3%에서 틀리는 것이다.

 

TC 도 다운받아서 다 확인해봐도 틀린 곳이 없는데 시작부터 틀린다는 것은 알고리즘에서의 문제보단 입력 처리에서 문제가 생겼을 확률이 컸다.

 

똑같은 로직을 가져가면서 처리를 좀 다르게 해주니 통과가 되었다.

 

문제 난이도와는 별개로 애를 먹었던 문제.

 

 

깊은 복사를했던것이 문제였다. 

 

깊은 복사를 제외하고 다시풀어보니 재귀로도 풀렸음.

 

두가지 방법을 다 첨부하겠습니다.

 

 

📝 해결전략

 

 

풀이법은 특별한 것 없이 너비우선탐색으로 접근해주었다.

 

큐에다가 시작 위치를 넣어주고 편의점의 위치를 순회한다.

 

만약 거리가 1000이내이면 움직일 수 있는 거리이므로 이동시킨뒤 해당위치를 큐에 넣어준다.

 

이런식으로 계속 돌면서 종착지까지 도착을 하는 경우가 단 한 번이라도 존재한다면, check 변수에 true를 할당하여

 

해당 테스트는 도착을 할 수 있는 경우라고 표시해주면 된다.

 

 

 

1) 큐 사용

 

 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const log = console.log;

const T = +input[0];
let idx = 1;

for (let i = 0; i < T; i++) {
  const bfs = (X, Y) => {
    const deque = [[X, Y]];
    while (deque.length) {
      const [x, y] = deque[0];
      deque.shift();
      if (Math.abs(x - festival[0]) + Math.abs(y - festival[1]) <= 1000) {
        check = true;
        return;
      }
      for (let k = 0; k < N; k++) {
        if (!visited[k]) {
          if (Math.abs(x - place[k][0]) + Math.abs(y - place[k][1]) <= 1000) {
            visited[k] = true;
            deque.push([place[k][0], place[k][1]]);
          }
        }
      }
    }
    return;
  };

  const N = +input[idx];
  idx += 1;
  const visited = Array.from({ length: N }).fill(false);
  const start = input[idx].split(' ').map(Number);
  let place = [];
  let check = false;
  for (let j = 1; j <= N; j++) {
    place.push(input[idx + j].split(' ').map(Number));
  }
  idx += N + 1;
  const festival = input[idx].split(' ').map(Number);
  idx += 1;

  bfs(...start);

  log(check ? 'happy' : 'sad');
}

 

2) 재귀 방식

 

 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const log = console.log;

const T = +input[0];
let idx = 1;

for (let i = 0; i < T; i++) {
  const bfs = (x, y, Visited) => {
    if (Math.abs(x - festival[0]) + Math.abs(y - festival[1]) <= 1000) {
      check = true;
      return;
    }

    for (let k = 0; k < N; k++) {
      if (check) return;
      if (!Visited[k]) {
        if (Math.abs(x - place[k][0]) + Math.abs(y - place[k][1]) <= 1000) {
          Visited[k] = true;
          bfs(place[k][0], place[k][1],Visited);
        }
      }
    }
  };

  const N = +input[idx];
  idx += 1;
  const visited = Array.from({ length: N }).fill(false);
  const start = input[idx].split(' ').map(Number);
  let place = [];
  let check = false;
  for (let j = 1; j <= N; j++) {
    place.push(input[idx + j].split(' ').map(Number));
  }
  idx += N + 1;
  const festival = input[idx].split(' ').map(Number);
  idx += 1;

  bfs(...start, visited);

  log(check ? 'happy' : 'sad');
}