문제

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

가희는 고구마가 먹고싶다! 하지만 가희에겐 T라는 시간제한이 존재한다.
T 시간안에 장애물을 피해 가희가 고구마를 가장 많이 먹을수 있는 경우를 출력하라!

입력

• 첫쨰줄에 맵의 세로크기 R, 세로크기 C, 이동 제한시간 T
  • $2 \leq R \leq 100$
  • $2 \leq C \leq 100$
  • $1 \leq T \leq 10$
• 두번째 줄부터 R+1번째 줄까지 길이가 C인 문자열이 입력됨.
  • 문자열중 G는 가희, S는 고구마, .는 빈칸, #은 벽을 나타냄

출력
가희가 먹을수 있는 고구마의 최대치를 출력!

정답 바로보기 > 정답코드

첫시도

const dfs = (visited, y, x, t, s, path) => {
  // 방문한적 있을시 그냥 나감
  // 시간 다됐으면 고구마 리턴
  if (visited[y][x] || t === T) {
    return result;
  }

  visited[y][x] = true;
  pos.forEach(([ny, nx]) => {
    const [py, px] = [ny + y, nx + x];
    if (canGoNext(py, px)) {
      const sweetPotato = board[py][px] === 'S' ? 1 : 0;
	  dfs(visited, py, px, t + 1, s + sweetPotato, [...path, [py, px]]),
    }
  });

};

visited를 사용해 dfs로 풀었는데 여기에 반례가 존재한다.
왔던길로 다시 되돌아갈수 있기에 visited로 true를 체크했던 부분으로 다시 되돌아갈수 있다.
그리고 visited[y][x] = true라 했기에 파라메터로 입력된 visited가 바뀌는게 아니라 원본이 변경된다.

두번째 시도

const dfs = (
  visited,  potatos,  y,  x,  by = 0,  bx = 0,  t = 0,  s = 0,
  reversed = false,  path = [],
) => {
  const swpt = potatos.map(v => [...v]);
  const v = visited.map(v => [...v]);
  v[y][x] += 1;

  if (swpt[y][x]) {
    swpt[y][x] = false;
    s++;
  }

  if (t === T || flag) {
    return s;
  }
  if (s === maxSp) {
    flag = true;
    return s;
  }

  let ss = s;
  for (let i = 0; i < pos.length; i++) {
    const [py, px] = [pos[i][0] + y, pos[i][1] + x];
    if (!canGoNext(py, px)) continue;
    if (T - t > T / 2 + 1 && v[py][px] < 2) {
      if (py === by && px === bx) {
        if (reversed) continue;
        ss = Math.max(
          ss,
          dfs(v, swpt, py, px, y, x, t + 1, s, true, [...path, [py, px]]),
        );
      } else {
        ss = Math.max(
          ss,
          dfs(v, swpt, py, px, y, x, t + 1, s, false, [...path, [py, px]]),
        );
      }
    }
    // // 절반넘게 갔으면 -> 되돌아가기 불가능
    else if (v[py][px] < 1) {
      ss = Math.max(
        ss,
        dfs(v, swpt, py, px, y, x, t + 1, s, false, [...path, [py, px]]),
      );
    }
  }

  return ss;
};

코드가 한눈에봐도 난잡해졌다...ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
우선 원본변수가 수정되는걸 막기위해 깊은복사를 해줬다.

const swpt = potatos.map(v => [...v]);
const v = visited.map(v => [...v]);

코드를 한번 설명하면 절반넘게 갔을경우 되돌아가지 않고
절반 이하로 갔을경우에만 되돌아갈수 있도록 짠 코드이다.
정말 탐색시간을 엄청나게 줄였다고 생각했지만 아무렇지않게 숨어서 시간을 갉아먹는 녀석이 있었다.

세번째 시도

두번째 시도에서 깊은복사 하는 부분이 문제가 됐었다.
너무 안풀려서 그냥 dfs로 탐색을 해도 똑같이 6%에서 시간초과가 난걸보고
dfs자체가 문제가 아니란걸 알았고, 배열을 깊은복사를 반복하는게 문제란걸 깨달았다.
그래서 저 부분을 없애고 visited[y][x]를 수정후에 dfs가 돌면 다시 복구시켰다.
다른사람들 코드를 보니까 이걸 백트랙킹이라고 한다.

정답코드

const stdin = require('fs').readFileSync(0, 'utf-8')
  .trim()
  .split('\n');
let line = 0;
const input = (() => {
  return () => stdin[line++].split(' ').map(v => +v);
})();
const input2 = (() => {
  return () => stdin[line++].split('');
})();

const [R, C, T] = input();
const board = Array.from({ length: R }, () => input2());
const visited = Array.from({ length: R }, () =>
  Array.from({ length: C }, () => 0),
);
const pos = [
  [-1, 0], // 상
  [1, 0], // 하
  [0, -1], // 좌
  [0, 1], // 우
];
const start = { y: -1, x: -1 };

for (let i = 0; i < R; i++) {
  for (let j = 0; j < C; j++) {
    if (board[i][j] === 'G') {
      start.y = i;
      start.x = j;
    }
  }
}

const canNotGoNext = (y, x) => {
  if (y >= 0 && y < R && x >= 0 && x < C && board[y][x] !== '#') {
    return false;
  }
  return true;
};

let max = 0;

const dfs = (v, y, x, t = 0, s = 0, path = []) => {
  // 고구마가 있고, 먹은적 없다면 s를 증가시킨다
  if (board[y][x] === 'S' && visited[y][x] === 0) {
    s++;
  }
  // t가 최대치에 도달했다면 거기까지만 탐색한다.
  if (t === T) {
    max = Math.max(s, max);
    return;
  }

  for (let i = 0; i < pos.length; i++) {
    const [ny, nx] = [pos[i][0] + y, pos[i][1] + x];
    // 갈수없는 곳이라면 다음곳을 탐색한다.
    if (canNotGoNext(ny, nx)) continue;

    // 한번 지나가면 1을 증가한다.
    v[y][x] += 1;
    // dfs문 
    dfs(v, ny, nx, t + 1, s, [...path, [ny, nx]]);
    // 다음 위치를 탐색하기전 되돌려둔다.
    v[y][x] -= 1;
  }
};

dfs(visited, start.y, start.x);
console.log(max);