[코테 준비/알고리즘] DFS BFS

1. DFS

• 정의
  • DFS는 깊이 우선 탐색라고 불림
  • 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조(혹은 재귀 함수)를 사용함

스택 자료구조
입구와 출구가 동일한 형태
사용하는 함수
  - stack<int> s;
  - s.top()
  - s.pop()
  - s.empty()

• 동작 과정
  1. 탐색 시작 노드를 스택에 삽입하고 방문처리 진행
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리함. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냄
  3. 끝날때 까지 반복함

• 여기 강의에선 재귀 함수로 이를 표현했음
• 재귀함수란..?

2. 재귀함수

• 재귀 함수란 자기 자신을 다시 호출하는 함수
• Python에서는 이러한 재귀함수를 스택형태로 메모리에 쌓아올리기에 특정 메모리 한계까지 반복적으로 쌓이면 에러 문구를 출력하게 함

재귀 함수의 예시

유킬리드 호제법 [알고리즘 단계]
  1. 두 정수 a와 b (a>b>0)를 준비합니다.
  2. a를 b로 나눈 나머지 r을 계산합니다. (r=a%b)
  3. r=0이면 b가 최대공약수입니다.
  4. r≠0이면 a를 b로, b를 r로 바꿔 2번으로 돌아갑니다.


예제 1: GCD(56, 42)
  1. a=56,b=42   >>   56÷42=1(몫), 나머지 r=14
  2. a=42,b=14   >>   42÷14=3 (몫), 나머지 r=0
  3. 나머지가 0이므로, GCD(56, 42) = 14

3. BFS

큐 자료구조

• 입구와 출구가 모두 뚫려 있는 터널과 같은 형태
• 사용하는 함수
  • queue<int> q;
  • q.push(1);
  • q.pop();
  • q.front()
  • q.empty()

4.예시

• 음료수 얼려 먹기
  • (0,0) 배열서부터 (L,RU,D) 한칸씩 +1할때 0이 있으면 그 다음 위치에 대해서 다시 (L,RU,D) 한칸씩 +1할때 0이 있는지 확인한다. 0이 없을때 까지 반복하고 다 완료하면 확인하지 않은 0의 노드로 다시 이 반복 과정을 진행한다.

int ice[N][M];
int check[N][M];//구지 사용하지 않아도 0을 1처리하면 됨
int dx[] = [0, 1, 0, -1];
int dy[] = [1, 0, -1, 0];
bool is_zero(int x, int y){
	if(x<1 || y<1 || x>N || y>N) 
		return false;
	if(ice[x][y]==0) {
		ice[x][y]=1;
		for(int i=0; i<4; i++){
			if[ice[x+dx[i]][y+dy[i]]==0]{
				is_zero(x+dx[i],y+dy[i]);
			}
		}
		return true;
	}
	return false;
}

• 미로 탈출
  • 괴물을 피해 최소 거리이기에 (1,1)에서부터 아래, 오른쪽, 왼쪽을 우선적으로 0이 이 아니라면 이동하여 오른쪽 맨 아래에 도달하도록 할 것이다.
  • 이때는 최소거리이기에 BFS를 사용해서 진행하자

int miro[N][M];
queue<int> q;
bool is_zero(int x, int y){
	q.push({x,y});
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		int nx = x + ?;
		int dx = y + ?;
		if(nx<1 || ny<1 || nx>N|| nY>M)
			continue;
		if(miro[nx][ny] == 1) {
			miro[nx][ny] = miro[x][y]+1; //값을 계속 변형하기에 접근한 노드에 대해서는 더이상 접근 못함
			q.push({nx,ny});
		}
	}
	return miro[N-1][M-1];
}