2023/10/20 TIL

오늘은 알고리즘 문제를 풀기위해 DFS 개념공부를 했다

깊이 우선 탐색(DFS, Depth-First Search)

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

해당 사진과 같은 과정으로 더 이상 갈 수 없게 되면 다시 가장 가까울 갈림길로 돌아와서 다른방향으로 탐색하는 것.
너비 우선 탐색(BFS)보다 좀 더 간단하지만 단순 검색 속도 자체는 느리다고 한다.
빨리 BFS도 공부해라!

얼핏 이해는 가지만 막상 구현하면 머리가 하얘지는 마술..ㅜㅜ 열심히 하자

StringTokenizer

어제 분명 Scanner보다 좋은 BufferedReader를 알게되어 잘 사용하고 있었는데
DFS문제를 풀다보니 다들 StringTokenizer로 입력값을 쪼개서 사용하고 있더라!

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int answer = 0;
String years = br.readLine();
String[] arr = years.split(" ");

나는 이렇게 split 메서드로 나눠서 입력값을 배열에 저장했는데 더 좋은 방법이 있다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
List<Integer> list = new ArrayList<>();

while (st.hasMoreTokens()) {
	int token = Integer.parseInt(st.nextToken());
	list.add(e);
}

오늘은 문제에 너무 매몰당해서 다른 일을 못했다 반성중..ㅠㅠ

---

Reference
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
https://gintrie.tistory.com/10