[JS] 코딩테스트 고득점 Kit - DFS/BFS한번에 정리하기

코테에 level 3이상은 안나오는 관계로, 먼저 level 2까지의 문제만 정리하고 차후 level3도 추가하겠습니다!

타겟넘버 level 2

function solution(numbers, target) {
    let count = 0;

    //변하는 값: index, curSum
    const dfs = (index, curSum) => {
        if(index == numbers.length){
            if(curSum == target)count++;
            return;
        }
        dfs(index+1, curSum + numbers[index]);
        dfs(index+1, curSum - numbers[index]);
    }
    dfs(0, 0);

    return count;

}

 

1. 함수 정의

• 입력으로 numbers 배열과 target 숫자를 받습니다.

2. 변수 초기화

• count라는 변수를 0으로 초기화합니다. 이는 목표 숫자를 만드는 방법의 수를 세는 데 사용됩니다.

3. DFS (깊이 우선 탐색) 함수 정의

• dfs(index, curSum)이라는 내부 함수를 정의합니다.
• index: 현재 처리 중인 숫자의 인덱스
• curSum: 현재까지의 합계

4. DFS 함수 로직

기저 조건:

• if(index == numbers.length): 모든 숫자를 처리했는지 확인합니다.
• 만약 모든 숫자를 처리했고, curSum이 target과 같다면 count를 증가시킵니다.
• 그리고 함수를 종료합니다.

재귀 호출:

• 현재 숫자를 더하는 경우: dfs(index+1, curSum + numbers[index])
• 현재 숫자를 빼는 경우: dfs(index+1, curSum - numbers[index])

5. DFS 시작

• dfs(0, 0)을 호출하여 탐색을 시작합니다.
• 초기 인덱스는 0, 초기 합계는 0입니다.

6. 결과 반환

• 모든 탐색이 끝나면 count를 반환합니다.

 

게임맵 최단거리 level 2

function solution(maps) {
    let xSize = maps[0].length;
    let ySize = maps.length;

    let queue = [[0, 0, 1]]; // [curX, curY, curNum]
    maps[0][0] = 0; // 시작점 방문 표시

    while (queue.length > 0) {
        let [curX, curY, curNum] = queue.shift();

        if (curX === xSize - 1 && curY === ySize - 1) {
            return curNum; // 도착점에 도달
        }

        // 4방향 탐색
        let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        for (let [dx, dy] of directions) {
            let nextX = curX + dx;
            let nextY = curY + dy;

            if (nextX >= 0 && nextX < xSize && nextY >= 0 && nextY < ySize && maps[nextY][nextX] === 1) {
                queue.push([nextX, nextY, curNum + 1]);
                maps[nextY][nextX] = 0; // 방문 표시
            }
        }
    }

    return -1; // 도달할 수 없는 경우
}

 

1. 함수 정의:

• solution(maps)라는 함수가 정의되어 있습니다.
• 입력으로 2차원 배열 maps를 받습니다.

2. 변수 초기화:

• xSize: 맵의 가로 크기 (열의 수)
• ySize: 맵의 세로 크기 (행의 수)
• queue: 시작점 [0, 0, 1]을 포함하는 배열 (x좌표, y좌표, 현재까지의 이동 횟수)

 

3. BFS (너비 우선 탐색) 시작:

• 시작점을 방문했다고 표시 (maps[0][0] = 0)
• queue가 비어있지 않은 동안 반복:

 

4. BFS 주요 로직:

a. 큐에서 현재 위치 정보를 가져옴:

• curX, curY: 현재 x, y 좌표
• curNum: 현재까지의 이동 횟수

b. 도착 확인:

• 현재 위치가 맵의 오른쪽 아래 끝이면 curNum 반환

c. 4방향 탐색:

• 상, 하, 좌, 우 네 방향에 대해 다음 위치 계산
• 각 방향에 대해:
  • 다음 위치가 맵 안에 있고, 갈 수 있는 곳(1)인지 확인
  • 조건을 만족하면 큐에 새 위치 추가 ([nextX, nextY, curNum + 1])
  • 해당 위치를 방문했다고 표시 (maps[nextY][nextX] = 0)

5. 결과 반환:

• 모든 탐색이 끝났는데도 도착점에 도달하지 못했다면 -1 반환