37.図形隣接行列の検索
グラフィック隣接行列の検索
鼻翼には草頭が止まっているような感じがします.どうしてもわからない!
リファレンスリファレンスリファレンスソースコードを参照してコードを記述し、デバッグを迂回していくつかの理解を行った.
首都コードを作成するときは、コードの役割を考慮し、コードのサイズを考慮してください.
ワンマン構成のコードですが、暗記した感じと言うべきでしょうか?
しかし、私はアルゴリズムをマスターしました.どうしてこんなに時間がかかるの...
结局今日はエピソード一つも理解できませんでした.休む.
もっと頑張ろうと思いますが、今日は反省の日です.function getDirections(matrix, from, to) {
// TODO: 여기에 코드를 작성합니다.
// 순차적으로 탐색할수있도록 queue를 만들고, 그 첫번째 인자로 from을 넣는다.
const queue = [from];
const inqueue = (n) => queue.push(n);
const dequeue = () => queue.shift();
//해당 행을 탐색했는지 확인하기위한 배열을 만든다.
const isCheckedRow = new Array(matrix.length).fill(false);
// 첫 정점 확인여부를 표시, 방문하지 않았을 경우 queue 추가되어 확인진행을함
// from은 queue에 들어있기 때문에 해당 행은 확인한것으로 취급
isCheckedRow[from] = true;
// 확인 로직 작성!
// queue와 while은 친구!!
// 확인할 행이 queue에 들어있기때문에 확인할 행이 빌때까지 확인반복
while (queue.length > 0) {
//queue의 0번째 인자를 꺼내고 확인용 행에 할당
const currentRow = dequeue();
//메트릭스의 행이 to과 같다면 간선이 연결된것
if (currentRow === to) {
return true;
}
// 현재행(정점)에 연결된(간선이있는) 정점들을 확인
// 간선 유무 확인
for (let i = 0; i < matrix[currentRow].length; i += 1) {
// 간선이있고 연결된 행을 확인하지 않았다면 해당 행을 queue에 할당.
if (matrix[currentRow][i] > 0 && !isCheckedRow[i]) {
//if(간선이면1, 1이면 truthy && 확인안됬으면 true)
// 확인 할 항목에 i를 추가 => 해당 행(matrix[i]행)을 확인목록에 추가
inqueue(i);
// 확인할 목록에 추가됫기때문에 해당행은 확인했음으로 처리
isCheckedRow[i] = true;
}
}
}
return false;
}
console.log(
getDirections(
[
[0, 1, 0, 1],
[1, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
],
1,
3
)
);
// > true
Reference
この問題について(37.図形隣接行列の検索), 我々は、より多くの情報をここで見つけました
https://velog.io/@hinyc/37.-graph-인접-행렬-찾기
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
function getDirections(matrix, from, to) {
// TODO: 여기에 코드를 작성합니다.
// 순차적으로 탐색할수있도록 queue를 만들고, 그 첫번째 인자로 from을 넣는다.
const queue = [from];
const inqueue = (n) => queue.push(n);
const dequeue = () => queue.shift();
//해당 행을 탐색했는지 확인하기위한 배열을 만든다.
const isCheckedRow = new Array(matrix.length).fill(false);
// 첫 정점 확인여부를 표시, 방문하지 않았을 경우 queue 추가되어 확인진행을함
// from은 queue에 들어있기 때문에 해당 행은 확인한것으로 취급
isCheckedRow[from] = true;
// 확인 로직 작성!
// queue와 while은 친구!!
// 확인할 행이 queue에 들어있기때문에 확인할 행이 빌때까지 확인반복
while (queue.length > 0) {
//queue의 0번째 인자를 꺼내고 확인용 행에 할당
const currentRow = dequeue();
//메트릭스의 행이 to과 같다면 간선이 연결된것
if (currentRow === to) {
return true;
}
// 현재행(정점)에 연결된(간선이있는) 정점들을 확인
// 간선 유무 확인
for (let i = 0; i < matrix[currentRow].length; i += 1) {
// 간선이있고 연결된 행을 확인하지 않았다면 해당 행을 queue에 할당.
if (matrix[currentRow][i] > 0 && !isCheckedRow[i]) {
//if(간선이면1, 1이면 truthy && 확인안됬으면 true)
// 확인 할 항목에 i를 추가 => 해당 행(matrix[i]행)을 확인목록에 추가
inqueue(i);
// 확인할 목록에 추가됫기때문에 해당행은 확인했음으로 처리
isCheckedRow[i] = true;
}
}
}
return false;
}
console.log(
getDirections(
[
[0, 1, 0, 1],
[1, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
],
1,
3
)
);
// > true
Reference
この問題について(37.図形隣接行列の検索), 我々は、より多くの情報をここで見つけました https://velog.io/@hinyc/37.-graph-인접-행렬-찾기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol