본문 바로가기

넓이우선탐색

 (2)
게임 맵 최단거리 난이도 level2 문제 programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 제한사항 maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다. n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다. maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자..
Breadth-first search 기본개념 알고리즘 공부를 시작하면서 생소한 단어들이 너무나 많고 개념도 잡히지 않은 상태 이기 때문에 간단히 정리 하고자 한다. 우선 넓이우선탐색(BFS)은 트리를 예로 들어서 많이 설명해 주는 것 같았고 반대되는 개념으로는 깊이우선탐색(Depth-First Search) 있다. 단어 뜻 그대로 가장 깊은곳을 먼저 탐색하느냐 or 내 주위에 가까운 곳부터 전부 탐색하고 다음 깊이의 단계를 탐색 할 것 인지를 구분하고 있다. 넓이 우선 탐색 은 물결처럼 퍼지듯 가까운 경로의 후보부터 탐색을 한다고 하는데 아래의 그림을 보면 바로 이해는 된다. 위의 그림에서 처럼 BFS 는 depth 가 같은 노드를 먼더 탐색하고 다음 depth로 이동 한다. 그런데 두 탐색알고리즘의 장점은 무엇일까?? 장점 1. BFS를 사용하면..

티스토리툴바