[JS] - DFS, BFS 알고리즘

기본 그래프 정의

let graph = Array.from(Array(n+1), () => []);
 for(let [x,y] of arr){
                graph[x].push(y);
                graph[y].push(x);
}

예제 - BFS (백준1697번 - 숨바꼭질)

문제링크 : https://www.acmicpc.net/problem/1697

문제

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다.
X-1 , X+1 , 2*X
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
-> 5-10-9-18-17 순으로 가면 4초

핵심

count를 +1 해주는 위치와 사용하는 방법이 중요 ~!
count를 방문 안했을시 방문 할 때마다 +1 해주면 다른 탐색도 거쳐와서 N == K 일때도 생길 수 있기 때문에 count 값이 크게 나온다. 때문에 e라는 점이 큐에 몇번째로 들어갔는지 판단후 +1 해주기 위해 count를 q에 같이 넣어줌으로써 해결했다.

코드

function answer(N,K){
            let Max = 10000
            let count = 0;
            let q = [];
            let visited = Array.from({length:Max+1} , ()=>false);
            function BFS(v){
                q.push([v,count]);
                while(q.length > 0){
                    let v = q.shift(); 
                    let e = v[0];
                    count = v[1]; 
                    if(!visited[e]){
                        visited[e] = true;
                        if (e === K){
                            return count;
                        }
                        count += 1;
                        if ((e*2) <= Max){
                            q.push([[e*2], count]);
                        }
                        if ((e+1) <= Max){
                            q.push([[e+1], count]);
                        }
                        if ((e-1) >= 0){
                            q.push([[e-1], count]);
                        }
                    }
                } 
                return count;
            }
            BFS(N);
            console.log(count);
        }

예제 - BFS (백준14503번 - 로봇 청소기 )

문제링크 : https://www.acmicpc.net/problem/14503

문제

1. 현재 위치를 청소한다.

2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
   a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   b.왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   c.네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   d.네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

기존의 BFS 구현에서 아래 2가지를 추가해주면 된다.

1. 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행하기 때문에 현재 방향을 왼쪽방향으로 바꿔주는 함수

2. 현재 방향을 기준으로 후진을 하기 위해서 역방향으로 바꿔주는 함수

코드

	//방향 전환
        function chage(d){ 
            if(d === 0) return 3;   //북 -> 서
            else if(d === 1) return 0; //동 -> 북
            else if(d === 2) return 1; //남 -> 동
            else if(d === 3) return 2; //서 -> 동
        } 
        function back(d){
            if(d === 0) return 2;  // 북 -> 남쪽 후진
            else if(d === 1) return 3; // 동 -> 서
            else if(d === 2) return 0; // 남 -> 북
            else if(d === 3) return 1; // 서 -> 동
        } 
        function answer(N,M,robot_arr,board){
            // 0 = 북 / 1 = 동 / 2 = 남 / 3 = 서 
            let dx = [0, 1, 0, -1];
            let dy = [-1, 0, 1, 0];
            let answer = 0; 
            let x = robot_arr[0];
            let y = robot_arr[1];
            let z = robot_arr[2];  // 로봇 방향 
            function BFS(row,col,d){
                answer = 1;
                board[row][col] = 2;  //청소한 경우 2로 변경
                let q = [[row,col,d]];  
                //console.log(q);
                while(q){ 
                    q_key = q.shift();
                    let row = q_key[0];
                    let col = q_key[1];
                    let d   = q_key[2]; 
                    console.log("#1",row,col,d);
                    let temp_d = d;
                    for (let i=0;i<4;i++){ 
                        temp_d = chage(temp_d); 
                        let new_row = row + dy[temp_d];
                        let new_col = col + dx[temp_d]; 
                        //console.log("#2",new_row,new_col , new_row >= 0 && new_row < N && new_col >= 0 && new_col < M && board[new_row][new_col] === 0);
                        if (new_row >= 0 && new_row < N && new_col >= 0 && new_col < M && board[new_row][new_col] === 0){
                            answer += 1;
                            board[new_row][new_col] = 2;
                            console.log("#2-1",new_row,new_col , temp_d , answer);
                            q.push([new_row, new_col, temp_d]); 
                            break;
                        }
                        else if(i === 3){
                            new_row = row + dy[back(d)]; 
                            new_col = col + dx[back(d)];
                            q.push([new_row,new_col, d]);
                            if (board[new_row][new_col] == 1){
                                //console.log(new_row , new_col)
                                return answer;
                            }
                        }
                    } 
                }  
            }
            BFS(x,y,z)  
        }

예제 - BFS (카카오커머스 - 가장먼거리 찾기)

• BFS 알고리즘에 거리를 계산해서 각 정점마다의 거리를 배열에 저장시킨다.

function bfs_kakao(arr , num){
            let n = 6;
            let graph = Array.from(Array(n+1) , () => []);
            let visited = new Array(n+1).fill(false);
            let dist = new Array(n+1).fill(0);
            let q = [];
            visited[1] = true;
            // 그래프 인접리스트 만들기 
            for(let [x,y] of arr){
                graph[x].push(y);
                graph[y].push(x);
            }
            q.push([1,num[0]]);
            while(q.length){
                const [v, curDist]  = q.shift();  // curDist 거리계산
                const adj = graph[v]; 
                for(let i=0;i<adj.length; i++){  // 연결노드개수만큼
                    const v = adj[i]; 
                   if(!visited[v]){
                       visited[v] = true; 
                       q.push([v,curDist+num[v-1]]);  
                   }
                }
                dist[v] = curDist;
            }
            console.log("dist",dist);
            return true;
        }

예제 - DFS (합이 같은 부분집합 구하기)

예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

DFS 풀이

function solution(arr){
                let answer="NO", flag=0;
                // reduce를 활용한 배열 합 구하기
                let total=arr.reduce((a, b)=>a+b, 0);
                let n=arr.length;
                function DFS(L, sum){
                    if(flag) return;
                    if(L===n){
                        if((total-sum)===sum){
                            answer="YES";
                            flag=1;
                        }
                    }
                    else{
                        DFS(L+1, sum+arr[L]);
                        DFS(L+1, sum);
                    }
                }
                DFS(0, 0);
                return answer;
            }
            let arr=[1, 3, 5, 6, 7, 10];
            console.log(solution(arr));

예제 - DFS (백준2667번 - 단지번호)

문제링크

문제

1. 첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

• 기본전인 DFS 문제에 카운팅 기능 추가

function answer(){
            const n = 7
            const arr = [
            [0,1,1,0,1,0,0],
            [0,1,1,0,1,0,1],
            [1,1,1,0,1,0,1],
            [0,0,0,0,1,1,1],
            [0,1,0,0,0,0,0],
            [0,1,1,1,1,1,0],
            [0,1,1,1,0,0,0]
            ]
            let answer = 0;
            let ans_map = [];
            const dx = [-1,0,1,0];
            const dy = [0,-1,0,1];
            let z = 0
            function DFS(x,y){
                arr[x][y]=2;
                z++; 
                for(let k=0;k<4;k++){
                    let nx=x+dx[k];
                    let ny=y+dy[k];
                    //0으로 된곳 2로 감염시키기
                    if(nx>=0 && nx<n && ny >=0 && ny<n && arr[nx][ny]===1){
                        DFS(nx, ny, z); 
                    }
                }
            } 
            //DFS(0,1,1); 
            for(let i=0; i<n; i++){
                for(let j=0; j<n; j++){
                    if(arr[i][j] === 1){ 
                        answer++; 
                        z = 0;
                        DFS(i,j); 
                        ans_map.push(z);
                    }
                }
            } 
        }

예제 - DFS (부분집합 기본)

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력
▣ 입력예제
3
▣ 출력예제
1 2 3
1 2
1 3
1
2 3
2
3

DFS 풀이

function solution(n){
 	let answer=[];
	let ch=Array.from({length:n+1}, ()=>0);
 		function DFS(L){
                    if(L===n+1){
                        let tmp="";
                        for(let i=1; i<=n; i++){
                            if(ch[i]===1) tmp+=(i+" ");
                        }
                        if(tmp.length>0) answer.push(tmp.trim());
                    }
                    else{
                        ch[L]=1;
                        DFS(L+1);
                        ch[L]=0;
                        DFS(L+1);
                    }
                }
                DFS(1);
                return answer;
            }

예제 - DFS,BFS (섬나라아일랜드)

상하좌우 + 대각선 범위 검색

DFS 풀이 재귀

function solution(board){
            let answer = 0;
            let n = board.length;
            let dx = [-1, -1, 0, 1,1,1,0,-1];
            let dy = [0,1,1,1,0,-1,-1,-1];
            function DFS(x,y){
                board[x][y]=0;
                for(let k=0; k<8; k++){
                    let nx=x+dx[k];
                    let ny=y+dy[k];
                    if(nx>=0 && nx<n && ny >=0 && ny<n && board[nx][ny]===1){
                        DFS(nx, ny); 
                    }
                }
            }
            for(let i=0; i<n; i++){
                for(let j=0; j<n; j++){
                    if(board[i][j] === 1){
                        answer++;
                        DFS(i,j); 
                    }
                }
            }
            return answer;
        }
        let arr = [[1,1,0,0,0,1,0],
            [0,1,1,0,1,1,0],
            [0,1,0,0,0,0,0],
            [0,0,0,1,0,1,1],
            [1,1,0,1,1,0,0],
            [1,0,0,0,1,0,0],
            [1,0,1,0,1,0,0]];
    console.log(solution(arr));
    ```

BFS 풀이

function solution2(board){
            let answer = 0;
            let n = board.length;
            let dx = [-1, -1, 0, 1,1,1,0,-1];
            let dy = [0,1,1,1,0,-1,-1,-1];
            let queue=[];
  	for(let i=0; i<n; i++){
		for(let j=0; j<n; j++){
                    if(board[i][j] === 1){ 
                        board[i][j] = 0;
                        queue.push([i,j]);
                        answer++;
                        while(queue.length){
                            let [x,y] = queue.shift();
                            console.log(x,y);
                            for(let k=0;k<8;k++){
                                let nx=x+dx[k];
                                let ny=y+dy[k];
                                if(nx>=0 && nx<n && ny>=0 && ny<n && board[nx][ny]===1){
                                    board[nx][ny]=0;
                                    queue.push([nx, ny]);
                                }
                            }
                        }
                        console.log("BFS end");
                    }
                }
            }
        }