문제 설명
나의 풀이
// Run by Node.js
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let N;
let count = 0;
const input = [];
rl.on("line", function(line) {
if (!N) {
N = line;
return;
}
if (count < N) {
input.push(line);
count++;
if (count === N) rl.close();
}
}).on("close", function() {
solution(N, input);
process.exit();
});
function solution(N, input) {
const adjMatrix = input.map((line) => line.split(' '));
const visited = Array.from({length: N}, () => new Array(N))
let mindistance = Infinity;
function dfs(x, y, distance) {
if (x >= N || y>= N || x < 0 || y < 0 || adjMatrix[x][y] === '0' || visited[x][y] === true) return;
if (x === N-1 && y === N-1) {
mindistance = mindistance > distance ? distance : mindistance;
}
visited[x][y] = true;
// 위로
dfs(x-1, y, distance+1);
// 아래로
dfs(x+1, y, distance+1);
// 왼쪽
dfs(x, y-1, distance+1);
// 오른쪽
dfs(x, y+1, distance+1);
visited[x][y] = false;
}
dfs(0,0,1);
console.log(mindistance);
}
풀이 회고
프로그래머스로 항상 풀다가 푸니 처음에 입력을 받는 것이 좀 낯설었다. N이라는 변수를 두고 첫번째 라인의 라인 수를 N에 저장을 하고 이후에 line들을 input에 넣어주는 방식으로 구현했다. count를 line을 input에 넣을 때마다 늘려줬는데 이 값이 N과 같아질 때 readline.close()를 해주었다.
이후에 문제는 dfs를 이용해서 해결했다. dfs 함수에서 해당 위치가 배열을 나갔거나 0이거나 방문한 적이 있으면 더 나아가지 않고 리턴을 해주었고 현재 위치가 끝인지 확인 후 현재까지 거리가 최소이면 최소 값을 수정해주었다. 그리고 재귀 함수로 다른 위치로 보내주었다.
👀