[Algorithm]

hyena_leeยท2023๋…„ 3์›” 18์ผ
0

Algorithm

๋ชฉ๋ก ๋ณด๊ธฐ
52/53
post-thumbnail

๐Ÿฆ• ์ธ์ ‘ ํ–‰๋ ฌ ๊ธธ์ฐพ๊ธฐ

๐Ÿ€ ๋ฌธ์ œ ํ’€์ด


// function getDirections(matrix, from, to) {
//   // ๋ฐฉ๋ฌธํ–ˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ๋ฐฐ์—ด
//   const map = matrix.map(a => [...a].fill(0));  // ๋ฐฉ๋ฌธ ์—ฌ๋ถ€

//   // ์žฌ๊ท€๋ฅผ ๋Œ๋ฆฌ๋ฉด์„œ ๊ธธ์ด ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ํ•จ์ˆ˜
//   const canGetDirections = (matrix, from, to) => {
//     if(matrix[from][to]) return true;

//     // [0, 1, 0, 0]
//     // [0, 1, 0, 0] from = 0, to = 2 0๋ถ€ํ„ฐ ๋‹ค๋ฅธ ๋…ธ๋“œ๊นŒ์ง€ ๊ฐ€๋Š” ๊ธธ์„ ํ™•์ธ ํ›„ ๊ทธ๋ฆฌ๊ณ  ๊ทธ ๊ธธ์„ ๊ฐ€๋ณธ์ ์ด ์žˆ๋ƒ
//     for (let i = 0; i < matrix[from].length; i++) {
//       if(i === from || i === to) continue;

//       // from ์ด ๋ฐ”๋€๋‹ค.
//       // ๊ธธ์ด ์žˆ๊ณ , ๋ฐฉ๋ฌดํ•œ์ ์ด ์—†์œผ๋ฉด ๊ฑฐ๊ธฐ๋กœ ๊ฐ€๊ฒ ๋‹ค.
//       if(matrix[from][i] && !map[from][i]) { //๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ธธ์ด ์žˆ๋‚˜
//       // ๊ฑฐ๊ธฐ๋กœ ๊ฐ€๋ฉด ์—ฌ๊ธฐ์„œ๋ถ€ํ„ฐ ๋‹ค์‹œ ์ฐพ๋Š”๋‹ค ๋ชฉ์ ์ง€๊นŒ์ง€ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ธธ์ด ์žˆ๋ƒ
//         map[from][i] = 1;  // ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ๋ฅผ ํ•ด์ค€๊ฑฐ
//         if(canGetDirections(matrix, i, to)) return true;   // ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ธธ๋ถ€ํ„ฐ ๋‹ค์‹œ ์ฐพ๋Š”๋‹ค.
//       }
//     }
//     return false;

//   }
//   return canGetDirections(matrix, from, to);

// }


// const a = [
//    [0, 1, 0, 0],
//		[0, 0, 1, 0],
//		[0, 0, 0, 1],
//		[0, 1, 0, 0]
// ]

// a[0][2] === 1;
// 0 -> 1 -> 2 truen;
// 1 ์ด๋ƒ ์•„๋‹ˆ๋ƒ


function getDirections(matrix, from, to, visited = []) {
  // if(from === to) {
  //   return true
  // }
  if(matrix[from][to] === 1) return true;
    visited[from] = true; // ํ˜„์žฌ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ–ˆ์Œ์„ ํ‘œ์‹œ

    // ๊ฐ„์ ‘์ ์œผ๋กœ ์ด์–ด์ง„ ๊ฒฝ์šฐ๋ฅผ ์ฐพ์•„์•ผํ•จ
    for (let i = 0; i < matrix[from].length; i++) {
      if(matrix[from][i] === 1 && !visited[i]) {
        if(getDirections(matrix, i, to, visited)) {
          return true
        }
      }
    }
    // ๋ฌดํ•œ ๋ฃจํ”„๋ฅผ ์–ด๋–ป๊ฒŒ ํ•ด๊ฒฐ?
    return false;
}

๐ŸŒฒ ํšŒ๊ณ 

profile
์‹ค์ˆ˜๋ฅผ ๋‘๋ ค์›Œ ๋ง๊ณ  ๊ณ„์† ๋„์ „ ํ•˜๋Š” ๊ฐœ๋ฐœ์ž์˜ ์—ฌ์ •!

0๊ฐœ์˜ ๋Œ“๊ธ€