풀어본 2차원 배열 문제 정리

1. Section 2_봉우리

• 기본 2차원 배열 문제이다.

function solution(arr) {
            // 회전방향 : 12시, 3시, 6시, 9시
            let dx = [-1, 0, 1, 0]; // 행
            let dy = [0, 1, 0, -1]; // 열
            let cnt = 0; // 봉우리 수

            // console.log(arr.length);
            for(let i=0; i<arr.length; i++){ // 행
                for(let j=0; j<arr.length; j++){ // 열
                    let flag = 1;
                    for(let k=0; k<4; k++){ // 회전방향 : 4개
                        let x = i+dx[k]; // x축 회전 좌표
                        let y = j+dy[k]; // y축 회전 좌표
                        if(x>=0 && x<arr.length && y>=0 && y < arr.length && arr[x][y] >= arr[i][j]){ 
                            // if 조건문 설명
                            // kx >=0 && kx < n : 0보다는 크지만, n보다는 작아야 한다 : 즉 범위 안에 들어야한다
                            // ky >=0 && ky < n : 0보다는 크지만, n보다는 작아야 한다 : 즉 범위 안에 들어야한다
                            // arr[kx][ky] >= arr[i][j] : 현재 좌표값(arr[i][j])보다 회전좌표 값(arr[kx][ky])이 더 크면 현재 좌표 봉우리 아님
                            flag = 0; // 봉우리 아님 표시
                            break;
                        }
                    }
                    if(flag) cnt++; // 봉우리 카운트
                }
            }

            return cnt;
        }

        let arr = [[5, 3, 7, 2, 3],
        [3, 7, 1, 6, 1],
        [7, 2, 5, 3, 4],
        [4, 3, 6, 4, 1],
        [8, 7, 3, 5, 2]];
        console.log(solution(arr));

2. Section 9_경로탐색(인접행렬)

• 인접행렬(2차원 배열)과 DFS 알고리즘

 function solution(n, arr){
                let answer = 0;
                // n+1한 이유는 arr의 정점이 1부터 시작하기 때문에 
                // 5행 5열로 하면 배열이 맞지가 않음
                let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0)); // 2차원 배열 => 간선 연결
                let check = Array.from({ length: n + 1 }, () => 0); // 1차원 배열 => 방문여부 체크
                let path = [];
                

                for(let [a,b] of arr){ // 간선연결
                    graph[a][b] = 1;
                }

                function DFS(depth){
                    if(depth === n) {
                        answer++;
                        console.log(path);
                    } else {
                        for(let i=1; i<=n; i++){
                            // depth정점에서 i로 갈 수 있는지 체크(즉, graph[a][b]가 1이면 갈 수 있음)
                            // check[i] 방문안했으면 Go
                            if(graph[depth][i]===1 && check[i]===0){
                                check[i] = 1; // 방문체크
                                path.push(i)
                                console.log(depth, ">>>>>>>>>>>>>> push", i)
                                DFS(i);
                                check[i] = 0; // 방문체크 해제
                                path.pop()
                                console.log(depth, "-------------- pop", i)
                            }
                        }
                    }
                }
                check[1] = 1; // 처음에 1은 체크 => 1번부터 방문해서 도니까!
                path.push(1);
                DFS(1);
                return answer;
            }

            let arr=[[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5]];
            console.log(solution(5, arr));

3. 미로탐색(DFS)

• 2차원 배열과 DFS

 function solution(board) {
            let dx = [-1, 0, 1, 0]; // 행
            let dy = [0, 1, 0, -1]; // 열
            let cnt = 0; // 경우의 수
            // console.log(board.length) // 7

            function DFS(x, y){
                if (x === 6 && y === 6) { // 도착점(6,6)
                    cnt++;    
                } else {
                    // for(let i=0; i<board.length; i++){
                    //     for(let j=0; j<board.length; j++){
                            for(let k=0; k<4; k++){ // 좌표회전
                                let nx = x+dx[k]; // x회전
                                let ny = y+dy[k]; // y회전
                                if (nx >= 0 && nx < board.length && ny >= 0 && ny < board.length && board[nx][ny] === 0) { // nx와 ny 범위 안에 있어야 함
                                    // if(board[nx][ny] === 0){
                                        board[nx][ny] = 1; // 방문
                                        DFS(nx, ny); // 한칸 증가
                                        board[nx][ny] = 0;
                                    // }
                                }

                            }
                        }
                //     }
                // }
            }
            board[0][0] = 1; // 첫 번째부터 시작이니까 방문함을 표시
            DFS(0, 0);
            return cnt;
        }

        let arr = [
            [0, 0, 0, 0, 0, 0, 0],
            [0, 1, 1, 1, 1, 1, 0],
            [0, 0, 0, 1, 0, 0, 0],
            [1, 1, 0, 1, 0, 1, 1],
            [1, 1, 0, 0, 0, 0, 1],
            [1, 1, 0, 1, 1, 0, 0],
            [1, 0, 0, 0, 0, 0, 0]
        ];

        console.log(solution(arr));

---

차이점

1. 봉우리문제는 기본 2차원 배열로 2중 For문을 이용해 전체 탐색
   j열을 돌면서 좌표 탐색하며 진행
2. 경로탐색-인접행렬은 탐색 가능한 좌표로 2차원 배열을 만들고, DFS로 방문여부를 체크하며 탐색
   탐색 가능한 좌표를 체크하며 깊이우선탐색((DFS)로 탐색
3. 미로탐색(DFS)는 탐색가능한 좌표를 주고 DFS로 방문여부를 체크하며 탐색
   x와 y를 매개변수로 받고 방문여부 체크하며 DFS로 탐색