BFS/DFS 기본기 연습

시작하기에 앞서...

보통은 다른 알고리즘 + 그래프 탐색으로 나올듯, 구현력 업을 위한 시뮬+그래프 탐색도 섞어 놨음

구현을 잘하자! 아이디어가 떠올라도 구현을 못하면 쓸모가 없음

 

이론

그래프의 특징

정점과 간선으로 이루어져 있음(Node정점, Edge간선이라고 함)

그래프는 순환 or 비순환 구조를 이룸 (문제에서 사이클이 존재하는지에 대한 여부)

그래프는 방향이 있는 유향 그래프와 방향이 없는 무향 그래프가 있음 (무향 그래프의 경우 양방향 이동이 가능)

간선이 방향을 가지는지에 따라 그래프를 잘 입력 받아야 함

그래프에 가중치(비용, 시간 등등)이 더해진다면 최소 비용(최단 거리) 문제가 됨

 

트리의 특징

사이클이 없음

하나의 루트(최상위 노드)를 가짐

부모 노드와 자식 노드의 관계가 존재함

방향이 있는 비순환 그래프라고 함

노드가 N개인 트리는 항상 N-1개의 간선을 가짐

임의의 두 노드 간의 경로가 유일하다. -> 두 정점간의 경로가 단 1개 뿐이다.

 

문제 팁

조건을 잘 읽고 입력을 잘 받자

- 방향이 있는/없는지

- 시작/종료 정점이 무엇인지

- 문제에 힌트가 있는지, 아래와 같이 힌트가 지문에 들어있는 경우들이 꽤 있음

  * 두 정점 사이를 연결하는 간선은 단 하나 뿐 이다.

  * 간선은 정확히 정점의 개수보다 하나 적으며, 모든 정점은 연결되어 있다.

- 그래프 그려가면서 풀기, 경험상 풀이 아이디어 떠올리기가 좋음 그리고 그려보는게 정확함

- 초기화 잘하기(방문 배열 초기화, 여러개의 그래프 입력 시에 그래프 vector 초기화 등)

 

BFS/DFS

그래프 탐색 기본(실버, 골드) _코드 자동으로 나와야 함

바이러스: https://www.acmicpc.net/problem/2606  ✅ 07.24

적록색약: https://www.acmicpc.net/problem/10026  ✅ 07.26

 

그래프 탐색 연습(골드)_구현 시간이 좀 걸릴 수도, 문제 이해 + 구현 + 그래프 탐색

연구소3: https://www.acmicpc.net/problem/17142  ✅ 08.06

숨바꼭질4: https://www.acmicpc.net/problem/13913 - 구현이 딱히 없음 !

벽 부수고 이동하기 4: https://www.acmicpc.net/problem/16946

치즈: https://www.acmicpc.net/problem/2638

스타트 택시: https://www.acmicpc.net/problem/19238

 

DFS 심화(사이클 판별)

텀 프로젝트: https://www.acmicpc.net/problem/9466

미로 보수: https://www.acmicpc.net/problem/30689

 

선분교차(골드1, 예전에 만났을 수도 있음)

버스 갈아타기: https://www.acmicpc.net/problem/2536

 

도전 문제(플래티넘)

수영장 사장님: https://www.acmicpc.net/problem/15730

숨바꼭질5: https://www.acmicpc.net/problem/17071 (이건 예전에 답지보고 풀었던듯...)

 

트리

트리에서의 그래프 탐색(골드)

트리: https://www.acmicpc.net/problem/1068

가장 가까운 공통 조상: https://www.acmicpc.net/problem/3584

트리의 지름: https://www.acmicpc.net/problem/1967

두 로봇: https://www.acmicpc.net/problem/15971