[백준/G4] 4485 녹색 옷 입은 애가 젤다지?

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

시간 복잡도

O(N * (N**2))

테스트케이스 갯수 * 다익스트라 수행

풀이

다익스트라를 활용, 최소값을 구함
최댓값을 담은 dist 배열을 별도로 사용해서 각 지점까지의 최소 비용을 업데이트
dist의 오른쪽밑끝에 도달한 값을 반환하여 출력

1차코드

const dx = [1, 0, -1, 0];
const dy = [0, -1, 0, 1];

function checkRupee(N, arr) {
  const dist = Array.from({ length: N }, () =>
    Array.from({ length: N }, () => Infinity)
  );

  // 초기값
  const q = [[0, 0]];
  dist[0][0] = arr[0][0]

  while (q.length > 0) {
    const [x, y] = q.shift();

    for (let d = 0; d < 4; d++) {
      let nx = x + dx[d];
      let ny = y + dy[d];

      if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue

      if (dist[nx][ny] > dist[x][y] + arr[nx][ny]) {
				dist[nx][ny] = dist[x][y] + arr[nx][ny]
        q.push([nx, ny]);
      }
    }
  }

	return dist[N-1][N-1]
}

// 링크가 이동하면서 얻는 최소 금액?
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./4485.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let idx = 0;
let tcNum = 0

while (idx < input.length) {
  const N = parseInt(input[idx]);
  if (N === 0) break;
  idx++;

  const arr = [];
  for (let i = 0; i < N; i++) {
    const row = input[idx].split(" ").map(Number);
    arr.push(row);
    idx++;
  }

  let answer = checkRupee(N, arr);
	tcNum++
  console.log(`Problem ${tcNum}: ${answer}`)
}

2차코드

const dx = [1, 0, -1, 0];
const dy = [0, -1, 0, 1];

function checkRupee(N, arr) {
  const dist = Array.from({ length: N }, () =>
    Array.from({ length: N }, () => Infinity)
  );

  // 초기값
  const q = [[0, 0, arr[0][0]]];
  dist[0][0] = arr[0][0];

  while (q.length > 0) {
    const [x, y, cost] = q.shift();

    if (cost < dist[x][y]) continue;

    for (let d = 0; d < 4; d++) {
      let nx = x + dx[d];
      let ny = y + dy[d];

      if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

			let newCost = dist[x][y] + arr[nx][ny]

      if (dist[nx][ny] > newCost) {
        dist[nx][ny] = newCost
        q.push([nx, ny, newCost]);
      }
    }
  }

  return dist[N - 1][N - 1];
}

// 링크가 이동하면서 얻는 최소 금액?
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./4485.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let idx = 0;
let tcNum = 0;

while (idx < input.length) {
  const N = parseInt(input[idx]);
  if (N === 0) break;
  idx++;

  const arr = [];
  for (let i = 0; i < N; i++) {
    const row = input[idx].split(" ").map(Number);
    arr.push(row);
    idx++;
  }

  let answer = checkRupee(N, arr);
  tcNum++;
  console.log(`Problem ${tcNum}: ${answer}`);
}

+) 큐에 현재까지의 값도 같이 가지고 가면서 미리 일부를 제외시키는 방법이지만
전체 N의 크기가 작아서 그런지(최대 125) 오히려 메모리와 시간이 증가했다

1차코드 14956kb 236ms
2차코드 19316kb 336ms