BFS / DFS

DFS : 

1) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

2) 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
3) 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다 (완전탐색)

특징 : 
1)자기 자신을 호출하는 순환 알고리즘의 형태 를 가지고 있다.
2)어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다

 

시간 복잡도:

DFS는 그래프 (정점의 수 : N, 간선의 수 : E)의 모든 간선을 조회한다.

  -인접 리스트로 표현된 그래프 : O(N+E)

  -인접 행렬로 표현된 그래프 : O(N^2)
출처 : https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

 

DFS 문제 : 

[정올 1169] 주사위 던지기1

원본 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=449&sca=50&sfl=wr_subject&stx=%EC%A3%BC%EC%82%AC%EC%9C%84&sop=and

문제 풀이 : 

: 순열 출력과 같은 문제

 

[정올 1889] N Queen

원본 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1162&sca=50&sfl=wr_subject&stx=queen&sop=and

문제 풀이 : https://gudwns999.tistory.com/104

일단 배치한 뒤 조건이 만족 안되면 백트래킹을 해가면서 마지막으로 배치 성공한 부분부터 다시 시작한다.

 

[] 더하기

원본 출처 :

문제 풀이 : https://gudwns999.tistory.com/105

: 조건에 맞지 않는 것들은 가지치기를 통해 더이상의 리컬시브가 돌지 않도록 한다.

 

BFS 문제 :

[정올 1661] 미로 탈출 로봇
원본 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=934&sca=50&sfl=wr_hit&stx=1661&sop=and

문제 풀이 : https://gudwns999.tistory.com/99?category=836032

: 현재 좌표에서 상하좌우로 갈 수 있는 좌표 중 조건에 만족하는 좌표를 큐에 모두 넣고 하나씩 빼면서 최종 조건을 만족하는지 물어본다.

 

[정올 1078] 저글링 방사능 오염

원본 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=358&sca=50&sfl=wr_subject&stx=%EC%A0%80%EA%B8%80%EB%A7%81&sop=and

문제 풀이 : https://gudwns999.tistory.com/100

:BFS를 돌면서 map에 cnt++ 값을 기록 해준다. 그 후 map에서 가장 큰 수에 +3 을 더하면 저글링이 마지막으로 죽는 시간이 된다. 다시 map을 돌며 저글링이지만 방문한적이 없는 저글링 수를 카운트 한다. 

 

[정올 1006] 로봇

원본 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=285&sca=50&sfl=wr_subject&stx=%EB%A1%9C%EB%B4%87&sop=and

문제 풀이 : https://gudwns999.tistory.com/101

: 방문체크에 방향축을 추가하여 체크해주어야 한다. 로봇은 회전을 하기 때문에 이동값 뿐만 아니라 회전한 뒤에 좌표도 큐에 넣어줘야 한다. 또한 로봇은 1~3칸을 가지만 벽이 있다면 벽을 뚫고 2칸을 이동할 수 없다. 때문에 앞에 벽이 있다면 2,3칸 가는 시도를 하면 안된다.

 

[코딩인터뷰완전분석] 자외선을 피해가기

원본 출처 : 

문제 풀이 : https://gudwns999.tistory.com/102

: BFS :자신이 이동하면서 현재 위치에서 다음에 갈 자외선+지금까지의 자외선의 합이 다음 위치에서의 자외선의 합보다 작다면 기록. 이런식으로 작은값만 찾아서 큐에 넣고 하나씩 빼보면서 끝날 때 까지 비교.

Heap : 힙트리에 push 하고 pop 하면 가장 작은값이 나오기 때문에 그 작은 값들로 최종 조건이 끝날 때 까지 반복.