[99클럽 코테 스터디] 📝 Day10. BFS (너비 우선 탐색)

99클럽 코테 스터디 10일차 TIL + BFS (너비 우선 탐색)

📍오늘의 학습 키워드

• 그래프 이론
• BFS (너비 우선 탐색)
• 완전 탐색
• 시간 및 공간 복잡도 분석

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

오늘은 송전탑 네트워크 문제를 해결하기 위해 그래프 이론과 BFS를 활용하여 전력망 문제를 해결하는 방법을 공부했다. 송전탑 네트워크와 전선들을 그래프로 표현하고, 각 전선을 하나씩 끊어서 두 개의 네트워크로 나누었다. 각 네트워크의 크기를 계산하여 송전탑 개수 차이를 최소화하는 방법을 배웠다. BFS 탐색을 통해 연결된 노드들의 개수를 효율적으로 셀 수 있다는 점도 확인했습니다.

📖 오늘의 회고

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

송전탑 네트워크 문제에서 전선을 끊었을 때 두 전력망의 송전탑 개수를 최대한 비슷하게 만드는 것이 어려웠다. 이를 위해 전선을 하나씩 끊어보고, 두 개의 네트워크로 나눈 후 각각의 크기를 계산하려고 시도했다.

🤔 어떻게 해결했는지

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

• 송전탑과 전선을 그래프로 표현했다.
• 각 전선을 하나씩 끊어보고, 두 개의 네트워크로 나누었다.
• BFS를 통해 각 네트워크의 크기를 계산했다.
• 각 경우의 네트워크 크기 차이를 계산하여 최소값을 업데이트했다.
• 최종적으로 송전탑 개수의 차이가 가장 작은 값을 찾았다.

🤓 무엇을 새롭게 알았는지

• BFS를 사용하여 그래프의 연결된 노드의 개수를 효율적으로 셀 수 있다는 것을 알게 되었습니다.
• 전선을 끊어서 그래프를 두 개의 컴포넌트로 나누고, 각각의 크기를 계산하는 방식으로 문제를 해결할 수 있다는 것을 배웠습니다.
• 시간 복잡도와 공간 복잡도를 고려하여 효율적인 알고리즘을 작성하는 방법을 알게 되었습니다.

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

• DFS (깊이 우선 탐색)와 BFS의 차이점과 각각의 활용 사례를 더 공부할 계획입니다.
• 더 복잡한 그래프 문제들을 풀어보면서 다양한 그래프 탐색 기법을 연습할 예정입니다.
• 시간 복잡도와 공간 복잡도를 더 깊이 이해하기 위해 알고리즘 분석을 공부할 계획입니다.