DFS : Depth-first search(깊이우선탐색)
Stack 을 사용하거나 재귀함수를 이용하여 구현한다.
또한 DFS는 백트래킹 알고리즘을 구현할때 자주사용된다(재귀함수)
재귀함수란 자기자신을 다시 호출하는 함수이다
이때 주의해야할 점은
1.재귀 함수가 종료되는 시점을 반드시 명시해야 한다.
2.재귀함수의 깊이가 너무 깊어지면 Stack overflow발생
DFS는 BFS와 달리 인접노드가 아닌 시작점에서 연결된 노드를 계속해서 찾는 알고리즘입니다. 더이상 찾을수 없을경우 올라와서 다시 찾는 것
시간복잡도는 BFS 와 동일합니다 O(V+E)
이차원 배열을 예로들어서 설명하자면
이중 for 문을 이용하여
방문하지 않았고 조건에 맞는다면 방문여부 체크 후 dfs 로 크기 구한 후 결과값 찾기.
bfs 와 dfs 의 차이점은 bfs 는 queue 에 넣고 뺀 값의 상,하,좌,우를 확인 후 queue에 넣고 빼고 반복하면서 인접노드들만 본다면 dfs 는 상하좌우를 확인하지만 확인후 바로 재귀함수를 실행해서 깊이 내려가는 것입니다.
예시코드
void dfs(y,x){
for(int i = 0; i < 4; i++){
ny = y + dy[i];
nx = x + dx[i];
}
if(영역 ex)0<=ny&& ny<N && 0<=nx && nx<N){
if(조건)
visited[ny][nx] = true
dfs(ny,nx);
}
}백트래킹이란 코딩테스트에서도 어려운문제에 해당한다. 문제를 보면 모든 경우의수를 확인해야 할때 가 존재하는데 for문으로는 비교해야하는 값의 깊이가 달라져서 사용하지 못할때가 많다 이때 dfs를 이용한 백트래킹 알고리즘을 사용해야한다.
순열:ex)m개중 n개를 뽑을 때 순서가 상관있는 것
예시문제는 주사위,사람들이 서있는 위치 등등 여러가지 순열문제일때 dfs를 사용하여 풀어야한다
예시코드
// 이때 num 은 깊이를 나타낸다 깊이란 번수를 나타냄
void dfs(int num,int n){
if(num ==n){
return
}
for(int i = 0;i < n;i++){
if(visited[i] == false){
visited[i] = true
dfs(num+1,n);
}
}
}시간복잡도는 중복가능이면 N^N (8까지)
중복 불가이면 N! (10까지)
풀어본 문제: 프로그래머스 단체사진찍기
링크:
https://velog.io/@cse05091/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Level2-4%EB%8B%A8%EC%B2%B4%EC%82%AC%EC%A7%84-%EC%B0%8D%EA%B8%B0
문제 코드를 보며 백트래킹을 정리 해보자면
순열 문제를 풀때 제한사항 등이 발생할 수있다.
문제를 예로 들자면 8명의 사람을 줄세우는데 제한사항을 맞춰 가능한 경우의 수를 구하는 것이다.
8명이기 때문에 for문을 8개를 쓴다면 시간복잡도가 엄청많이 나게된다.
그래서 재귀함수를(dfs)를 써서 나타낸 것이다.
맨 처음 dfs 를 실행할때 0을 넣는 것 대신 String""을 넣어주고 즉 0부터 시작하는 것으로 볼수있다(깊이) 깊이를
