[백준][DFS][난이도:하] 차이를 최대로 (10819번)

1.  문제

■ URL : https://www.acmicpc.net/problem/10819

■ 난이도 : 하 (DFS 기본문제)

 

2. 핵심요약

■ 문제유형 : 깊이우선탐색(DFS) 알고리즘

 

3. 문제풀이 접근

■ 선행학습 : DFS를 이용하여 리스트의 순열을 구현할 수 있어야 한다.

    - 참고: https://languagestory.tistory.com/403

[DFS] 순열(permutation)

 

4. JavaScript 코딩

// 로컬 환경에서 입력을 받을지, stdin에서 받을지 결정하는 변수
let isLocal = true;
 
let fs = require('fs'); // 파일 시스템 모듈을 사용하여 파일 읽기
let input;
 
// 로컬 환경일 경우 파일에서 입력을 읽어옴, 그렇지 않으면 stdin에서 읽어옴
if (isLocal) {
    input = fs.readFileSync('./10819.txt').toString().split('\n'); // 파일에서 입력 받기
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n'); // stdin에서 입력 받기
}
 
// 첫 번째 줄: 배열 A의 갯수 N을 입력 받기
let n = Number(input[0]);   // n: 배열 A의 크기
let arr = input[1].split(' ').map(Number); // 두 번째 줄: 배열 A의 원소들을 입력받아 arr 배열에 저장
let visited = new Array(n).fill(false); // 방문 여부를 추적하는 배열 (각 원소는 false로 초기화)
 
// 결과 변수 초기화: 가능한 값 중 가장 큰 값인 `max`를 구할 것
let max = -1e9; // `max`를 매우 작은 값으로 초기화
let result = []; // DFS에서 사용할 부분 배열
 
// 깊이 우선 탐색(DFS) 함수 정의
const dfs = (depth) => {
    // 종료 조건: 배열을 모두 탐색했다면
    if (depth === arr.length) {
        let sum = 0;
        
        // 배열이 완성되었으므로 인접한 원소들 간의 차이의 절댓값의 합을 구함
        for (let i = 0; i < n-1; i++) {
            sum += Math.abs(result[i] - result[i+1]); // 인접한 원소의 차이의 절댓값을 더함
            max = Math.max(max, sum); // 최대값을 갱신
        }
        return max; // 최대값을 반환
    }
 
    // 배열의 모든 원소에 대해 재귀적으로 DFS 탐색
    for (let i = 0; i < n; i++) {
        // 이미 방문한 원소는 다시 선택하지 않음
        if (visited[i]) continue;
 
        // 현재 원소를 방문하고 배열에 추가
        visited[i] = true;
        result.push(arr[i]);
 
        // 다음 원소를 탐색하기 위해 DFS 호출
        dfs(depth + 1);
 
        // 탐색을 마친 후, 방문을 해제하고 마지막 원소를 제거
        visited[i] = false;
        result.pop();
    }
}
 
// DFS 탐색 시작
dfs(0);
 
// 결과 출력: 가장 큰 차이 합을 출력
console.log(max);
 

 

5. 참고

https://languagestory.tistory.com/380

[DFS] 개념(Depth First Search; 깊이 우선 탐색) - 자바스크립트