2021년 5월 16일 코드스테이츠 DAY-42 자료구조 코플릿 문제

저번주 목요일(5. 13. ~ 5. 15.)부터 블로깅을 하지 않았다.

 

자료구조에서 매우 절었기 때문인데

 

개념을 이해했다고 생각했으나 코플릿을 통해 응용하는 과정에서는

 

맥을 못추었다. 

 

침착하게 다시 돌아보는 와중에 14일에 풀지 못했던 문제를 푸는 과정 중 

 

AHA 모먼트가 있었던 것을 적어보고자 한다. 

 

인접행렬에서 정점과 정점이 이어져 있는지 여부를 반환하는 문제였고

 

스프린트 리뷰시간에서 코드스테이츠 스태프는 이 문제를 큐로 풀었다는데 글쎄...

 

나는 이 문제는 재귀로 해결하여야한다라고 생각했다.

 

첫번째 시도

function getDirections(matrix, from, to) {
//범위를 초과해서 from과 to가 입력되면 false를 리턴
	if (from + 1 > matrix.length || to + 1 > matrix.length || from < 0 || to < 0) {
		return false;
	}
//from에서 to까지가 1이면 return true;
  if(matrix[from][to] === 1){
    return true
  }
//from에서 to까지 바로가는 길이 없다면 from에 연결된 다른 정점을 통해서 갈 수 있는지 탐색하는 과정
  for(let i = 0; i < matrix.length; i++){
    if(matrix[from][i] === 1){
//from에서 연결된 정점을 본 함수에 넣고 
      if(getDirections(matrix, matrix[from][i], to){
        return true
      }
    
  }return false;
}

이건 논리가 완벽한데? 라는 우매한 생각을하며 테스트를 하였으나 당연히 fail이었다. 

  for(let i = 0; i < matrix.length; i++){
    if(matrix[from][i] === 1){
//from에서 연결된 정점을 본 함수에 넣고 
      if(getDirections(matrix, matrix[from][i], to){
        return true
      }
    }

이 부분 중 matrix[from][i]를 getDirections 함수의 from자리에 넣는다면 from에는 0 혹은 1만 올 수 있는 것이다.

 

그리고 if(matrix[from][i] === 1)이라는 조건만 넣어서 필터링 시

 

자기자신이 다시 from에 들어갈 수 있어서 무한루프를 돌게 된다.

 

이를 개선해서 

 

두번째 시도 

function getDirections(matrix, from, to) {
  let pass = [from];

	if (from + 1 > matrix.length || to + 1 > matrix.length || from < 0 || to < 0) {
		return false;
	}
  
  if(matrix[from][to] === 1){
    return true
  }

  for(let i = 0; i < matrix.length; i++){
    if(matrix[from][i] === 1 && pass.includes(i) === false){ 
    //일단 from에는 0, 1보다 더 큰 수가 들어올 수 있으므로 pass.includes(matrix[from][i])는 들어갈 수 없다. 그리고 i가 includes의 괄호안에 들어와야하는 이유는
    //from이 3이고 to가 2일 경우로 예시를 들 수 있다. 3에서 2로가는 직접적인 길은 없는 것이고 그렇기에 3에서 연결된 다른 길이 2로 연결되는지를 조회해야한다.
    //그것이 바로 위 for 반복문과 if 조건문인데  matrix[from][i]가 1인것을 찾되 현재의 예시는 1이 3보다 먼저 있기에 답이 나오겠지만 matrix[3][3]이 1이라고 가정하고 3을 먼저조회한다고 가정할 경우에는
    //getDirections(matrix, 3, 2)와 같은 애초의 똑같은 함수를 불러오게 된다. 이는 무한루프에 빠지는 것을 초래할 수 있다. 
    //그러므로 matrix[from]의 배열의 인덱스에서 from자기 자신과 만나지 않게하기 위한 툴이 pass.includes(i) === false인 것이다. 
    //또한 pass.includes(i) === false를 사용하기 위해서 from을 pass라는 배열에 담아 놓은 것이다. 
 
      if(getDirections(matrix, i, to)){ //matrix[from][i]가 말이 안되는이유가  저 자리에 올 수 있는 것은 0,1 은 물론이고 더 큰수가 올 수 있음에 
        return true
      }
    }
  }return false;
  
  //from에서 to까지가 1이면 return true;
  //matrix.length[i][from] 1로 되있는게 있니? 있으면 걔네들을 from으로 넣어서 재귀 
  //없으면 false
}

위에서 예시를 든 배열은 아래와 같다. 

const result = getDirections(
	[
		[0, 1, 0, 0],
		[0, 0, 1, 0],
		[0, 0, 0, 1],
		[0, 1, 0, 0],
	],
	0,
	2
);

이번에는 통과하리라라고 시도했지만 또 fail.

 

왜일까? from이 재귀함수 속에서 계속 새로워 지는 과정중에 pass 배열 또한 초기화되기 때문이다. 

 

이를 막아주기 위해서는 pass가 함수밖에 있어야하는데 이는 코플릿에서 허용이 안되니 

 

함수안에 함수를 만드는 것이 답이리라.

 

세번째 시도

function getDirections(matrix, from, to) {
  let pass = [from];
  let findDirection = function (matrix, from, to) {
    if (matrix[from][to] === 1) {
      return true;
    }
    for (let i = 0; i < matrix[from].length; i++) {
      if (matrix[from][i] === 1 && pass.includes(i) === false) {
        if (findDirection(matrix, i, to)) {
          return true;
        }
      }
    }
    return false;
  };
  return findDirection(matrix, from, to);
}

 

SUCCESS