백준/ Gold 5 문제 , 백준 Node.js 자바스크립트 14503 , 로봇 청소기 [구현, 시뮬레이션]

백준/ Gold 5 문제 , 백준 Node.js 자바스크립트 14503 , 로봇 청소기 [구현, 시뮬레이션]

 

 

 

야아아아ㅏ아아아아악!!!!!!!!

 

 

풀이 시간

 

 

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

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

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

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

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

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

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
진짜 fucking hell 문제... 몇번을 울부짖은지 모르겠다.
방향 조절하는 부분이 너무 어려웠다.

 

 

 

문제 출처

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

14503번: 로봇 청소기

 

 

 

 

풀이

 

참고로 이 문제는 삼성 기출 문제이다.

 

내가 느끼기에 제일 시간 많이 쓰이고 어려운 문제는 풀릴듯 안풀릴듯. 테스트케이스는 다 돌아가는 데 새로운 반례하나가 걸릴때. 이럴때인거 같다.

 

 

처음에 접근했을때는 그닥 어렵게 느껴지지 않았다.

 

근데 풀다보니 어라? 하는 순간들이 있었는데, 

 

1. 네방향 모두 확인하고 원래방향 유지한채 후진할 때

2. 이동한 다음에 이동한 방향을 기준으로 왼쪽부터 탐색할 때

 

이다.

 

1번은 금방 해결했지만, 2번이 진짜...

 

맞냐 이게?

서쪽으로 이동하면 남쪽부터 탐색하고 남쪽에서 돌다가 북쪽으로가면 다시 서쪽부터 탐색하고... 홀리쉣...

 

이게 말로는 쉬워보이는데 일반화해서 코드를 짜는게 너무 안짜졌다.

 

처음엔 for문의 인덱스를 활용해서 해볼려했지만 반례가 자꾸 생겨서 

 

3시간 정도 풀다가 결국 다른 풀이를 참고했는데,

 

애초에 방향시작 자체부터 다르게 짠거같다. 

 

 

나는 0이 북쪽이라 탐색은 서쪽부터하니까

 

dx=[0, -1, 0, 1]

dy=[-1, 0, 1, 0]

 

로 처음에 설정했었는데, 이 인덱스를 맞출려고 하다보니까 더 안풀렸던것 같다.

 

이렇게 초기값을 설정하고.

 

 

 

(방향 + 3) % 4 라는 공식을 사용하면 이동하는 방향을 기준으로 왼쪽부터 순서대로 탐색할 수 있다.

 

이때 처음 방향을 옮겨 다음방향으로 다시 초기화시켜줘야한다.

 

 

 

또한 check 변수를 통해서 네방향을 돌아 한곳이라도 청소할 곳이 있는지 확인해주고 

 

청소할 곳이 없다면 원래의 방향을 기준으로 뒤쪽으로 한칸 이동시켜준다.

 

이때, 뒤로 이동한다고 방향에 변화가 있어서는 안된다.

 

 

 

 

---

다른 로직들은 다 잘 짰었는데, 저 (방향 + 3) % 4 를 생각해내지 못해어서 자꾸 이것도 해보고 저것도 해본 것 같다.

 

이동하면서 탐색하는 문제들은 나름 자신있는 문제들이였는데, 이런 유형의 문제는 또 새롭다.

 

 

나름 유명한 문제라 유튜브의 풀이도 있고, 다른 풀이가 많으니 여러 풀이를 참고하길 바란다.

 

 

 

 

 

정답

 

 

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

const [N, M] = input.shift().split(" ").map(Number);
const [r, c, d] = input.shift().split(" ").map(Number);
const MAP = [];
input.map((v) => {
  MAP.push(v.trim().split(" ").map(Number));
});

function solution(N, M, r, c, d, MAP) {
  let dq = [[r, c, d]];
  let cnt = 1;
  MAP[r][c] = 2;
  let dx = [-1, 0, 1, 0];
  let dy = [0, 1, 0, -1];
  while (dq.length !== 0) {
    let [X, Y, dr] = dq[0];
    let origin_dr = dq[0][2];
    dq = dq.splice(1);
    let check = false;
    for (let i = 0; i < 4; i++) {
      let next_dr = (dr + 3) % 4;
      dr = next_dr;
      let [mx, my] = [X + dx[next_dr], Y + dy[next_dr]];
      if (MAP[mx][my] === 1) continue;
      if (MAP[mx][my] === 0) {
        MAP[mx][my] = 2;
        cnt += 1;
        dq.push([mx, my, next_dr]);
        check = true;
        break;
      }
    }
    if (check === false) {
      if (origin_dr === 0) X += 1;
      else if (origin_dr === 1) Y -= 1;
      else if (origin_dr === 2) X -= 1;
      else if (origin_dr === 3) Y += 1;
      if (MAP[X][Y] == 1) return cnt;
      dq.push([X, Y, origin_dr]);
    }
  }
  return cnt;
}
console.log(solution(N, M, r, c, d, MAP));