DFS&BFS 정복

[wooyn730]

DFS&BFS 정복

정의

• DFS: 너비 우선 탐색
  • 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색
• BFS: 너비 우선 탐색
  • 현재 정점에 연결된 가까운 점들부터 탐색

구현 방법

• DFS: 재귀, 스택
• BFS: 큐

문제 유형

• 경로의 특징 저장: DFS
• 최단거리: BFS
• 그래프의 모든 정점 방문: 둘 다 가능
  • (추천 방식)
  • 대상 그래프 규모가 정말 크다면 DFS
  • 규모가 크지 않거나 대상이 별로 멀지 않다면 BFS

---

[백준] DFS+BFS 필수 문제

[프로그래머스] DFS&BFS C++ 문제

[wooyn730]

바이러스

사이트: 백준 번호: 2606 난이도: 실버3

풀이

• DFS - 재귀 (01/12)
• DFS - 스택 (01/13)
• BFS (01/14)

[wooyn730]

DFS와 BFS

번호: 1260 사이트: 백준 난이도: 실버2

풀이

• DFS - 스택, BFS (01/14)
• DFS - 재귀, BFS (01/15)

[wooyn730]

촌수계산

번호: 2644 사이트: 백준 난이도: 실버2

풀이

• DFS - 재귀 (01/15)
• DFS - 스택 (01/16)
• BFS (01/16)

[wooyn730]

미로 탐색

번호: 2178 사이트: 백준 난이도: 실버1

풀이

• BFS (01/19)

[wooyn730]

단지번호붙이기

번호: 2667 사이트: 백준 난이도: 실버1

풀이

• BFS (01/19)
• DFS - 스택 (01/20)
• DFS - 재귀 (01/20)

[wooyn730]

숨바꼭질

번호: 1697 사이트: 백준 난이도: 실버1

풀이

• BFS (01/21)

---

ㅋㅋ ㅠ

1. 메모리 초과 visit 검사 안해줌, 범위 제한 안해줌

2. OutOfBounds 처음에 visit 먼저 검사했다가 여기서 out of bounds 나는 거 모르고 헤멤 이렇게 넣으면 범위 검사 이전에 visit 체크해서 안됨

[wooyn730]

안전 영역

번호: 2468 사이트: 백준 난이도: 실버1

풀이

• BFS (01/22)
• DFS - 스택 (01/25)
• DFS - 재귀 (01/25)

[wooyn730]

토마토

번호: 7569 사이트: 백준 난이도: 골드5

풀이

• BFS (01/26)

간만에 골드인데 혼자 푼 건 시간초과해서 풀이 참고해서 풀었다..

알게된 것

1. 큐 데이터형을 구조체로 할 수 있다
2. BFS도 입력과 동시에 큐에 넣으면 시간을 단축할 수 있다
3. 꼭 BFS를 함수로 빼지 않아도 된다

[wooyn730]

스타트링크

번호: 5014 사이트: 백준 난이도: 실버1

풀이

• BFS (01/30)

---

visit[up] = true; 해줘야되는데 true 처리 안해서 헤멤.. 바본가

[wooyn730]

로봇 청소기

번호: 14503 사이트: 백준 난이도: 골드5

풀이

• DFS - 재귀 (01/31)

---

동서남북 이동이 헷갈려서 실패했던 것 같다..

[wooyn730]

맥주 마시면서 걸어가기

번호: 9205 사이트: 백준 난이도: 골드5

풀이

• BFS (02/02)
• DFS - 스택 (02/02)

---

visit을 2차원으로 했을 때 실행 중단됨... (이유 못찾음) 하지만 생각해보니 1차원이 필요했던거라 한 번에 통과

코드 길이는 그냥 주석 차이..

[wooyn730]

타겟 넘버

번호: 43165 사이트: 프로그래머스 난이도: 레벨2

풀이

• DFS - 재귀 (02/03)

---

DFS BFS 생각 안하고 떠오르는 대로 재귀 함수 짰더니 쉬웠다

[wooyn730]

네트워크

번호: 43162 사이트: 프로그래머스 난이도: 레벨3

풀이

• BFS (02/03)
• DFS-재귀 (02/03)

---

레벨3은 첨이라 긴장했는데 DFS&BFS 공부를 차근차근 해둬서 쉬웠다

[wooyn730]

게임 맵 최단거리

번호: 1844 사이트: 프로그래머스 난이도: 레벨2

풀이

• BFS (02/06)

---

어렵지 않았음 최단거리 == BFS 바로 떠오름 구조체 사용하는 것도 바로 떠올리기!

[wooyn730]

단어 변환

번호: 43163 사이트: 프로그래머스 난이도: 레벨3

풀이

• BFS (02/08)

---

이번에도 한 번에 통과 자신감이 생긴다 ^_^b

[wooyn730]

여행경로

번호: 43164 사이트: 프로그래머스 난이도: 레벨3

풀이

• DFS-재귀 (02/11)

---

보고풀었다... ㅠㅠ

기존 코드는 4개의 테케 중 절반 밖에 통과하지 못했다. 이유는 끊어진 경로를 생각하지 못해서 => 즉 백 트래킹을 못해서...

백 트래킹을 좀 공부하고 연습해야겠다.

또한 깊이/너비 탐색 문제를 평소 풀던 것처럼 2차원 int에 저장해야된다고 생각해서 find()를 사용해 엄청 이상한 코드를 만들었다.. (덕분에 vector에서 find() 함수 사용하는 법은 익혔지만..)

뻘짓했던 코드

[wooyn730]

토마토

번호: 7576 사이트: 백준 난이도: 골드5

풀이

• BFS (02/16)

3차원으로 풀었던 거랑 99퍼 유사한데 헷갈리면 우짜뇨...

[wooyn730]

DFS BFS 필수 문제집 (백준)은 모두 풀었으나 좀 더 풀어볼 것

옵션: DFS or BFS + 맞은 사람순 + 안 푼 문제 + 만명 이상 푼 문제

링크

좀 더 풀고 3월 내로 블로그 포스팅 ㄱㄱ

[wooyn730]

• 유기농 배추
• 영역 구하기
• 나이트의 이동

[wooyn730]

보물섬

번호: 2589 사이트: 백준 난이도: 골드5

풀이

• BFS

한 번 틀림 최단거리 중 최대거리를 구해야 했으므로 BFS 돌리되 visit을 초기화해줬어야함