bfs8 [알고리즘] 7-8 송아지 찾기 - BFS(넓이우선탐색)(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다. 문제 설명 : 수직선상 좌표에서 현수의 위치에서 송아지의 위치까지 갈 수 있는 최소한의 점프 횟수를 구하는 문제(한 번의 점프로 앞으로 1 or 뒤로 1 or 앞으로 5 이동 가능) 문제 링크 : https://cote.inflearn.com/contest/10/problem/07-08 풀이 최단 경로를 구하는 문제이기 때문에 BFS(넓이우선탐색)을 사용한다. 풀이 과정을 트리 그림으로 나타내면 다음과 같다. 노드의 숫자는 좌표 위치를 뜻하고 간선 위의 숫자는 한번의 점프로 이동하는 거리를 나타낸다(불필요한 중복 좌표는 생략). 즉, 트리의 레벨이 점프 횟수를 나타내고 최초로 송아지의 위치가 발.. 2021. 6. 16. [알고리즘] 7-7 이진트리 순회 - BFS(넓이우선탐색)(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다. 문제 설명 : 이진트리를 넓이우선탐색(BFS)하는 문제 넓이우선탐색(BFS)란 시작 정점으로부터 가까운 정점을 우선적으로 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 탐색 방법으로 다음과 같은 순서로 탐색이 진행된다. 시작 정점으로부터 가까운 정점을 우선적으로 방문한다는 것은 시작 정점과 연결된 간선의 수가 적다는 것을 의미하기 때문에, 트리의 낮은 레벨부터 마지막 레벨까지 순차적으로 정점을 방문하며 탐색을 진행하게 된다. 코드 깊이 우선 탐색과 달리 재귀적으로 구현하지 않음 Queue 자료구조를 이용해서 구현한다. 어떤 정점을 방문했을 때, 자신을 출력하고, 자식이 있다면 큐에 넣는다. .. 2021. 6. 15. 이전 1 2 다음
