๐ง codingtest/javascript 100์
๋ฌธ์ 74. ์ต์ฅ ๊ฒฝ๋ก ์ฐพ๊ธฐ
awesomeyelim
2022. 4. 13. 13:39
728x90
์ ๋ ฅ๋ฐ์ ๋์ ์ ์ด ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋์ด ์ฃผ์ด์ง๋,
๋ ์ ์ ์ฌ์ด๋ฅผ ์ด๋ํ ์ ์๋ ์ต์ฅ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์ฌ๋ผ.
- ์ด๋ ์ต๋จ ๊ฑฐ๋ฆฌ๋, ์ ์ ์ ์ค๋ณต์์ด ํ ์ ์ ์์ ๋ค๋ฅธ ์ ์ ๊น์ง ๊ฐ ์ ์๋ ๊ฐ์ฅ ๋ง์ ๊ฐ์ ์ ์๋ฅผ ์๋ฏธ
// ๋ฐ์ดํฐ
graph = {
1: [2, 3, 4],
2: [1, 3, 4, 5, 6],
3: [1, 2, 7],
4: [1, 2, 5, 6],
5: [2, 4, 6, 7],
6: [2, 4, 5, 7],
7: [3, 5, 6],
};
// ์
๋ ฅ
1 2
// ์ถ๋ ฅ
6
๋ฏธ๋ฆฌ ์๊ฐํด ๋ด์ผํ ๊ฒ
- ๋๋น์ฐ์ ํ์์ ์ด์ฉ
- ์ต์ฅ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ์ฐ ํ๋ก๊ทธ๋จ ๋์ํ ํด๋ณด๊ธฐ(์ด๋ฐ์์ ๊ฑฐ๋ฆฌ๊ณ์ฐ์ผ๋ก ์งํํ๋ค)
๋ต
let graph = {
1: [2, 3, 4],
2: [1, 3, 4, 5, 6],
3: [1, 2, 7],
4: [1, 2, 5, 6],
5: [2, 4, 6, 7],
6: [2, 4, 5, 7],
7: [3, 5, 6],
};
// let ์
๋ ฅ = prompt('์
๋ ฅ์ฐ').split(' ');
let ์
๋ ฅ = ["1", "7"];
let start = Number(์
๋ ฅ[0]);
let end = Number(์
๋ ฅ[1]);
let queue = [start];
let visited = [];// ๋ฐฉ๋ฌธํ ๋
ธ๋๊ฐ ๋์ ๋๊ฒ, ๊ฐ๊ฐ์ length๋ฅผ ๊ตฌํ๋ฉด์ ๊ฐ์ฅ ํฐ๊ฐ์ด ๋ฐํ๋๋๋กํจ
function ์ต์ฅ๊ฑฐ๋ฆฌ(q, visited) {
let node = q[q.length - 1];
let length = 0;
if (node == end) {
return visited.length;
}
if (visited.includes(node)) {
return visited.length;
} else {
visited.push(node);
}
let max = [];
for (let i in graph[node]) {
q.push(graph[node][i]);
max.push(length, ์ต์ฅ๊ฑฐ๋ฆฌ(q, visited));
length = Math.max.apply(null, max);
queue.pop();
}
return length; //์ต๋๊ฐ์ ๋ฐํํจ
}
console.log(์ต์ฅ๊ฑฐ๋ฆฌ(queue, visited));