[99클럽 코테 스터디] 📝 Day12. DFS/백트래킹

부제 : TMI 허리디스크가 재발하여 병원을 다니며,,, 1일1커밋을 이번주 못했다.. 한 번에 몰아넣기...아쉽다. 야근도 하고 회사 다니면서 공부하는 모든 직장인 화이팅 ㅠㅠ

건강도 챙겨야하고 개발자 시장에서 도태되지않도록 공부도 꾸준하게 하고 인간관계도 노력해야하고 가족들도 챙겨야하고 인간의 삶..^^ 재밌네..

 

99클럽 코테 스터디 12일차 TIL + DFS

 

📍 오늘의 학습 키워드

• DFS (깊이 우선 탐색)
• 백트래킹
• 그래프 탐색
• Java 자료구조 및 내장 함수 활용

📝 공부한 내용 본인의 언어로 정리하기

오늘은 DFS와 백트래킹을 활용해 주어진 항공권을 모두 이용하여 "ICN" 공항에서 출발해 모든 공항을 방문하는 경로를 찾는 문제를 풀어보았다. DFS는 한 경로를 끝까지 탐색하는 방식으로, 백트래킹은 조건에 맞지 않는 경로를 되돌아가 다른 경로를 탐색하는 방식이다. 이를 통해 주어진 조건을 만족하는 모든 경로를 탐색하고, 가능한 경로가 여러 개일 경우 알파벳 순으로 앞서는 경로를 찾았다.

📖 오늘의 회고

📚 어떤 문제가 있었고, 나는 어떤 시도를 했는지

처음에는 주어진 항공권을 어떻게 효율적으로 관리하고 탐색할지 고민이 많았다. 특히, 가능한 경로가 여러 개일 경우 알파벳 순으로 앞서는 경로를 선택하는 부분에서 어려움을 겪었다. 이를 해결하기 위해 그래프를 구성하고, 각 출발지에서 가능한 도착지를 정렬하여 탐색하는 방식을 시도했다.

🤔 어떻게 해결했는지

🔖 참고링크 (https://develop-tracking.tistory.com/75)

그래프를 구성할 때 HashMap을 사용하여 각 출발 공항을 키로, 도착 공항들의 리스트를 값으로 저장했다. 각 도착지 리스트를 알파벳 순으로 정렬하여 DFS 탐색 시 사전 순으로 경로를 선택하도록 했다. 또한, DFS와 백트래킹을 통해 모든 경로를 탐색하면서 조건에 맞는 경로를 찾았다.

🤓 무엇을 새롭게 알았는지

DFS와 백트래킹을 활용하면 복잡한 경로 탐색 문제를 효율적으로 해결할 수 있다는 것을 알았다. 또한, Java의 다양한 자료구조와 내장 함수를 활용하여 그래프를 구성하고 정렬하는 방법을 배웠다. 특히, computeIfAbsent와 같은 함수를 통해 간결하고 효율적으로 코드를 작성할 수 있었다.

⏳ 내일 학습할 것은 무엇인지

내일은 BFS(너비 우선 탐색) 알고리즘을 공부하고, 이를 활용한 문제 풀이를 시도해볼 것이다. BFS와 DFS의 차이점을 이해하고, 각각의 장단점을 비교하여 어떤 상황에서 어떤 알고리즘을 사용하는 것이 더 적합한지 학습할 것이다. 또한, 더 복잡한 그래프 탐색 문제를 해결해보면서 그래프 이론에 대한 이해를 깊게 할 것이다.