탐색

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말합니다
대표적인 그래프 탐색 알고리즘 : DFS/FS
코딩테스트에서 매우 자주 등장하는 유형!!

스택 자료구조

먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
입구와 출구가 동일한 형태로 스택을 시각화
ex. 박스 쌓기

연산 : 삽입 ,삭제

파이썬은 기본 객체인 리스트를 이용해서 append로 삽입, pop으로 삭제를 할 수 있다

큐 자료구조

먼저 들어온 데이터가 먼저 나가는 형식(선입 선출)의 자료구조
입구와 출구가 뚫려있는 터널로 시각화할 수 있다

파이썬에서는 리스트로도 구현이 가능하지만 deque라는 라이브러리를 이용하면 훨씬 빠르게 할 수 있다
=> 리스트는 pop을 써서 하면 나머지 값들이 위치 조정을 하는데 시간이 필요함

• append() : 오른쪽에서 하나 넣기 (시간복잡도 O(1))
• popleft() : 왼쪽에서 하나 삭제 (시간복잡도 O(1))
• reverse(): 역순으로 바꾸기

재귀 함수

자기 자신을 다시 호출하는 함수
단순한 형태의 재귀 예제

• 재귀 함수를 호출합니다
• 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지를 출력한다
• while, for문을 이용하지 않고 반복 가능
• 무한 루프를 이용하는 것이 아니라면 종료 조건을 반드시 명시해야 한다

자신을 호출하고 바로 다음 함수를 호출해서 마지막 함수가 종료한 뒤에 (100에서 리턴) 99부터 종료를 하는 방식 (스택 : 선입후출!)

cf. 파이썬은 재귀를 호출하는 것에 대한 제한이 있다
스택 프레임에 함수가 계속 쌓이는 것
-> stack 자료구조 안에 함수의 정보가 차례대로 쌓이므로 컴퓨터 메모리가 부족해진다

예제1 : 팩토리얼

예제2 : 최대공약수 계산(유클리드 호제법) - GCD (Greates Common Divisor)

(a, b)의 순서는 중요하지 않다 : else에서 순서를 뒤집어서?

재귀 함수 사용 유의 사항

잘 활용하면 복잡한 알고리즘 직관적이고 간결하게 작성

• 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용해야 한다
  모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다
  재귀 함수가 반복문보다 유리/불리 가능 (그러므로 문제를 만났을 때 잘 판단하기)
  컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다
• 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다
  ex. DFS 구현할 때 재귀함수 이용

DFS

• 깊이 우선 탐색
• 그래프에서 깊이를 우선적으로 탐색하는 알고리즘
• 스택 자료구조(혹은 재귀함수)를 이용
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다
  2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리
     방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

인접한 노드가 여러개면 문제에서 요구하는 조건에 따라 방문 순서를 정한다
-> 이 문제에서는 번호가 낮은 노드부터!

파이썬 소스코드

0번보다는 1번부터 노드가 많이 시작해서 graph의 0번째는 주로 빈배열
방문 정보 표현할 visited라는 1차원 리스트를 만든다 (1번부터 하기 위해 개수+1만큼의 개수)

자바스크립트 소스코드

let visited = new Array(graph.length+1).fill(false) 
let stack = [];

function dfs(index){ 
    if(visited.filter(el => el === true).length === graph.length+1)return; 
    
	visited[index] = true
    stack.push(index)

    for(let g of graph[index]){ // [2,3,8]
    	if(!visited[g]){
        	dfs(g) //true, push는 다음 단계에서 해준다
    }
     
}

BFS

• 너비 우선 탐색
• 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조를 이용

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다
2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다 (하나씩이 아니라 인접한 노드 "모두"!)
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다
   => 최단 거리 구할 때 많이 사용하는 방법

큐는 이전에 방문한 노드들을 바로 바로 뺀다

같은 레벨 : 1 / 238 / 7 4 5 / 6
-> 작은 값부터 순회해서 2쪽인 7먼저, 3쪽은 4,5가 다음 / 가장 깊은 6이 마지막

파이썬 소스코드

자바스크립트 소스코드

const BFS = (graph, startNode) => {
  const visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { 
  // 탐색해야할 노드가 남아있다면
  
    const node = needVisit.shift(); 
    // queue이기 때문에 선입선출, shift()를 사용한다.
    
    if (!visited.includes(node)) { 
    // 해당 노드가 탐색된 적 없다면
      visited.push(node); 
      needVisit = [...needVisit, ...graph[node]]; 
      //선택한 노드의 인접 값들을 push
      //...needVisit을 통해 가로를 먼저 간다
    }
  }
  return visited;
};

console.log(BFS(graph, 1));

문제1. 음료수 얼려먹기

• 0끼리 상하좌우로 연결
• 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수

세로 N, 가로 M
두번째 줄부터 N+1번째 줄까지 얼음 틀의 형태
구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1

한 번에 만들 수 있는 아이스크림의 개수를 출력한다

//큐에 넣어서 방문할 때마다 뒤로 넣고 앞으로 빼는 형태 
//있으면 계속 아래로 (BFS 안에 DFS) 

[0,1,4]  //0인 값들 구해서 queue에 넣고 인접을 다 구한 다음 queue의 남은 값들을 돈다  
[0,1,2] //n까지 확인하고 삭제, 없으면 다시 위로 돌아가서 인접 확인
[],
[0,1,2,3]



0인 애들을 모두 true로 바꾼다
1. 인접한 애들 다 구하기 start, end
2. 아래로 내려가서 start~end에서 찾기 / 이 중 겹치는 부분을 다시 start, end로 갱신 
3. 아래로 다시 가서 새로운 start, end에서 다시 찾기 

다시 처음으로 올라가서 true을 제외하고 0을 다시 찾는다 
첫줄에서 모두 true가 되면 
다음 줄부터 시작

def dfs(x,y){ 
	if(x<=-1 || x >=n || y<=-1 || y>=m){return false}
    if(graph[x][y] === 0) { 
    graph[x][y] =1
    dfs(x-1,y) //상하좌우는 방문처리를 하기 위해서만 사용 
    (많은 dfs 연산을 해도 모든 dfs를 끝내고 true를 리턴하는 것은 마찬가지)
    dfs(x,y-1)
    dfs(x+1,y)
    dfs(x,y+1)
    return True//여기서는 이미 
    }else{ 
    return False
    }
}

graph = []; 
result = 0; 
for(let i=0; i<n; i++){ 
  for(let j=0; j<m; j++){ 
  	if(dfs(i,j) === True){ result += 1} 
    //모든 노드를 방문해도 방문하면 1로 바꾸니까 중복 걱정 X
  }
}

console.log(result)

특정 지점에서 DFS/BFS 실행해서 이동 가능한 모든 노드에 대해 방문처리를 하고, 1은 방문할 수 없도록 하면 된다.

자바스크립트 풀이

function solution(graph, n, m){
    function dfs(x,y){
        if(x<0 || x>=n || y<0 || y>=m)return false
        if(graph[x][y] === 0){
            graph[x][y]=1;
            dfs(x-1,y)
            dfs(x+1,y)
            dfs(x,y-1)
            dfs(x,y+1)
            return true
        }else{
            return false
        }
    }

    let result=0;

    for(let i=0; i<n; i++){
         for(let j=0; j<m; j++){
            if(dfs(i,j))result++;
         }
    }
    return result;
    
}

문제2. 미로 탈출

내 풀이

function solution(graph, n, m){
let cnt=0; 
	function dfs(x,y){
    if(x<1 || x>n || y<1 || y>m){ return cnt; }
    if(graph[x][y] === 1){
   		 cnt++;
      dfs(x,y+1)
      dfs(x,y-1)
      dfs(x+1,y)
      dfs(x-1,y)
    }else{ 
    	return cnt;
    }
    } 
    
    return dfs(1,1)
}

강의 풀이

BFS : 간선의 비용이 모두 같을 때 최단 거리를 탐색하기 위해 사용할 수 있는 알고리즘

• queue에 넣어서 1인 경우에만 bfs 진행
• 매번 새로운 노드를 방문할 때 이전 노드 +1로 거리를 표시함

let dx = [-1, 1, 0, 0]
let dy = [ 0, 0, -1, 1]

function dfs(x,y){
let queue = [];
queue.push([x,y])

while(queue.length >0){ 
	let [x,y] = queue.shift() 
    for(let i=0; i<4; i++){
    	let nx = x + dx[i]
        let ny = y + dy[i]
        
        if(nx <0 || nx >- n || ny <0 || ny >=m){ continue; }
        if(graph[nx][ny] === 0){ continue; }
        if(graph[nx][ny] === 1){ 
        	graph[nx][ny] = graph[x][y]+1 //이전 노드에 +1한 값
            queue.push([nx, ny])
    }
    return graph[n-1][m-1]

}

}