2022-07-10
🚩DFS와 BFS에 관하여
사실 문제를 풀다보면 dfs와 bfs문제의 유형은 너무나 명확히 드러나는 경우가 많은 것 같다.그래도 그만큼 출제가 제일 많이되는 알고리즘으로서 간단하게 정리를 해놓을려고 한다
먼저 dfs를 문제와 bfs 문제를 풀 때 제일 크게 특징적으로 나뉘는 경우는
DFS문제는 대체로
경로의 특징을 저장해두어야 하는 문제
BFS문제는 대체로
(가중치가 없는)최단경로문제
(가중치가 있게 될 경우 최단경로문제는 다익스트라나 플로이드 워셜로 빠질 수 있게 된다)
라고 볼 수 있을 것 같다
🚩DFS에 대하여
DFS는 깊이 우선 탐색방식으로 딱 느낌적으로 먼저 전달을 해주자면 하나를 잡고 그 하나의 하나를 또 하나의 하나의,,,,이렇게 밑으로 내려가는 느낌이다.
기본적인 특징으로는
1.우선 시작 노드에서 방문하지 않은 인접노드를 큐에 삽입을 해준다(방문표시를 했음을 의미한다)
2.그러고 나면 더 이상 방문할 수 없을 때까지 탐색을 하고 안되면 이전 상태로 돌아오게 된다(백트래킹)
포인트:재귀!!
🔑장점
dfs는 기본적으로 재귀함수 형태나 스택으로 구현으로 하기에 계속 밑으로 깊이 내려가는 형태로
목표노드가 깊은 단계에 있을경우 해를 빨리 구할 수 있다
🔑단점
그만큼 깊이 내려가는만큼 상대적으로 검색속도가 bfs보다는 느리고
얻어진 해가 최단경로가 된다는 보장이 없다
대체로 따라서 검색보다는 순회를 할 경우에 많이 쓰인다.
기본적인 코드의 패턴은
def dfs(arr,cur,visited):
visited[cur]=True
for i in arr[cur]:
if not visited[i]:
dfs(arr,i,visited)즉 현재노드의 인접한 노드들을 순회하면서 방문을 하지 않았더라면 그 다음 노드에 대하여 진행을 해주면 된다
🙋♂️문제:재귀횟수가 너무 많아질 수 있다,,,
하지만 대체로 dfs에서 문제가 생기는 경우는 재귀횟수가 너무 많아지게 되면 프로그램이 끝나버리는 경우가 있기에 해당케이스를 유념해두자
import sys
sys.setrecursionlimit(100000)
#재귀의 허용깊이를 늘려줌🚩BFS에 대하여
bfs는 너비 우선 탐색방법으로서 사실 많은 문제가 bfs 위주로 풀어도 대부분 풀리는 것이 상대적으로 dfs보다 많은 것 같다.왜냐하면 bfs는 우선적으로 위에서부터 차근차근 하나씩
탐색하면서 내려가기에
최단경로 보장
이라는 특징이 너무 크기 때문이다.
포인트:deque!!(큐를 이용하여)
기본적인 특징으로는
1.시작노드에서 방문하지 않은 인접노드를 큐에 삽입
2.큐가 빌때까지(while q)하나씩 꺼내서 또 인접노드를 큐에 삽입해준다
(경고) 방문 Check를 반드시 큐에 '넣기 전'에 해주어야 한다.
큐에서 빼낸 후 방문check를 해주어도 로직상으로는 문제 없지만
불필요한 방문이 큐에 쌓이기 때문에 중복으로 방문되는 경우가 많이 생겨서 메모리 초과가 발생한다.
코드의 기본적인 패턴구성은
from collections import deque
def bfs(arr,start,visited):
queue=deque([start])
visited[start]=True
while queue:
cur=queue.popleft()
for i in arr[cur]:
if not visited[i]:
queue.append(i)
visited[i]=True
큐에 처음에 넣고 다시 빼고 인접한 것 넣어주고~반복
🔑장점
검색하는 속도는 훨씬 dfs보다 빠르다
🔑단점
그만큼 사용되는 메모리양도 dfs보다 훨씬 많게 된다
왜냐하면 현재의 경로말고도 다른경로에 대해서도 정보를 갖고있어야 하기에
🚩문제를 풀면서 느낀 점
1.대체로 얼음연결하기 문제,독립한 섬의 개수와 같은 문제들은 dfs로 풀면 잘 풀린다(쭉 파고 들어서 어디까지 되는지)
대체로 이런문제는 해당 dfs함수에서 return True,False를 반환해서 해당 값으로 True일 때에 카운트를 증가시켜서 독립한 개수들을 파악할 수 있다
2.대부분의 문제는 bfs로 문제를 풀어보아서 안되면 dfs로 풀어보고 효율성 통과를 못할경우 메모이제이션 같은 스킬을 추가적으로 넣어보는 방식으로 진행할 수 있을 것 같다
3.미로찾기같이 2차원 리스트 주고 경로 찾는 문제에서는
dx=[-1,1,0,0]
dy=[0,0,1,-1]
네 방향을 조절 해줄 수 있는 offset을 만들어 계산하자
nx=curr+dx[i]
ny=curr+dy[i]
요런방식
4.동시다발적으로 한 곳에서 스타트하는 bfs 문제가 아닐경우에는 미리 해당 1이나 즉 출발할 수 있는 곳들의 위치들을 다 찾아서 queue에 넣어놓고 해당 queue에 대해서 bfs를 돌리면 된다
5.특정 일직선에서 어떤 지점까지 가고자 할때의 필요한 시간이나 그런걸 물어보면 bfs로해서 나중에 -1을 해줘서 값을 반환해주자.왜냐하면 처음에 스타트 지점에 방문한걸위해 1을 쓸테니.그리고 범위도 꼭 넣어서 검사해주자.방문처리만 하면 안되는게 해당 범위를 벗어나면 인덱스 에러날수있음
if 1<=next_<=F and (not visited[next_]):
q.append(next_)
visited[next_]=visited[now]+1
