BFS3 [문제] BFS (미로 탈출) - 20210609 시작시간 : 23시 30분 종료시간 : 6월 10일 00시 13분 문제 : 동빈이는 N × M 크기의 직사각형 형태의 미로에 갇혔다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다 동빈이의 위치는 (1, 1)이며 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다 참고자료 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음, 한빛미디어 옮김 풀이 : 자바 결과 회고 : 참고 : https://goo.. 2021. 6. 10. [예제] BFS - 20210609 시작시간 : 01시 05분 종료시간 : 01시 21분 문제 : BFS를 이용하여 탐색 풀이 : 자바 결과 회고 : 진도가 밀린 부분이라 코드 따라가기로 공부! 와우! Queue! 참고 : https://freedeveloper.tistory.com/273 2021. 6. 9. 탐색 알고리즘(DFS, BFS) DFS (Depth First Search), 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 BFS (Breadth First Search), 너비 우선 탐색이라는 의미를 가진다. 쉽게 말해 가까운 노트부터 탐색하는 알고리즘이다. DFS 방식 : A-B-D-E-F-C-G-H-I-J, 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가면서 순회함 BFS 방식 : A-B-C-D-G-H-I-E-F-J, 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들(형제 노드들)을 먼저 순회함 참고 : https://saegeullee.github.io/algorithm/bfs-dfs 2021. 6. 3. 이전 1 다음
