티스토리 뷰

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

 

1103번: 게임

줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는

www.acmicpc.net

 

DP

DFS

 

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

const [N, M] = input.shift().split(" ").map(Number);
const board = input.map((v) => v.split(""));
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];

let dp = Array.from(Array(N), () => Array(M).fill(-1));
dp[0][0] = 1;

let visited = Array.from(Array(N), () => Array(M).fill(false));
visited[0][0] = true;
let answer = 1;

const dfs = (x, y, visited) => {
  const cnt = dp[x][y];
  const value = board[x][y];

  for (let i = 0; i < 4; i++) {
    const nx = x + value * dx[i];
    const ny = y + value * dy[i];

    if (nx >= 0 && ny >= 0 && nx < N && ny < M && board[nx][ny] != "H") {
      if (visited[nx][ny]) {
        process.exit(console.log(-1));
      }
      if (dp[nx][ny] >= cnt + 1) {
        continue;
      } else {
        if (answer < cnt + 1) answer = cnt + 1;
        dp[nx][ny] = cnt + 1;
        visited[nx][ny] = true;
        dfs(nx, ny, visited);
        visited[nx][ny] = false;
      }
    }
  }
};

dfs(0, 0, visited);
console.log(answer);

 

bfs로 풀다가 dfs로 바꿨다. 아직도 언제 bfs를 써야 되는 건지, 언제 dfs를 써야 되는 건지 모르겠다.

728x90
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/05   »
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
글 보관함