BFS2 그래프 & DFS/BFS 문제 풀이 지난 게시물에서 그래프와 그래프 순회에 대한 강의를 듣고 내용을 정리하여 포스팅했었다. 이번에는 강의 내용을 활용하여 풀었던 문제들을 짧게 공유한다. 문제들은 대부분 백준 문제집의 DFS+BFS 필수 문제 에 속한 문제들이다. 백준 2178번 이차원 배열 형태의 미로를 탐색하며, 출발점부터 도착점까지의 최소 거리를 구하는 문제이다. BFS/DFS 문제를 제대로 푸는게 처음이라, 공부한 개념을 적용하기 조금 어려웠는데 다음과 같이 풀었다. BFS로, 시작점(0, 0)에서부터 순회를 시작한다. 미로는 길이 존재하고, 현재 접점과 인접한 사방의 접점으로만 진행할 수 있다. 따라서 순회 시 이를 전부 체크한다. 위의 조건을 만족하며 아직 방문하지 않은 인접점은 방문 처리 후 BFS 탐색 큐에 넣어줌으로써, 다.. 2023. 11. 19. 그래프 + 그래프 순회 정리 요즘 소소한 알고리즘 스터디를 하고 있다. 매주 주제를 정해서 하루에 하나씩 문제를 풀고 있는데, 이번주 주제가 DFS/BFS였다. DFS/BFS 공부를 할 겸, 그래프와 순회 강의를 들으며 정리한 것을 간략히 기록한다. 강의는 Udemy에 있는 JavaScript 알고리즘 & 자료구조 마스터클래스 이다. 그래프 (Graph) : 노드/점들의 집합으로 구성된 데이터 구조 → 간단히 말해, 노드와 노드 간의 연결(Connection)로 이루어진 구조이다 어디에 사용되나? 그래프는 다양한 곳에 사용된다. 밑의 리스트는 한 번쯤 주변에서 경험해봤을, 그래프의 사용처들이다. SNS: Facebook이나 인스타그램 등. 사용자 간의 팔로우 관계가 그래프로 나타난다. Location Mapping 각종 추천 시스.. 2023. 11. 17. 이전 1 다음
