Breadth First Search 썸네일형 리스트형 [BFS]BJ_2146, 다리 만들기 0 또는 1로 이루어진 100 x 100 배열에 대해서 0을 1로 채워가면서 연결되는 최소길이를 구하는 문제이다. 어떻게 접근해야 할까? 일단 격자 형태로 좌/우/상/하를 탐색하는 문제의 경우에는 BFS부터 검토해 보는 것이 좋다. 보통의 BFS 문제가 격자를 바탕으로 이루어지기 때문이다. 이 문제도 확장 형태를 보면 BFS로 풀리는 문제라는 것은 어렵지 않게 유추할 수 있다. 다만, 어려운 점은 시작위치와 도착 위치를 어떻게 잡느냐이다. 시작 위치를 어디로 잡아야 할까? 문제에서 시작 위치와 도착 위치가 정해지는 경우는 시작위치를 queue에 넣고 탐색을 진행하되 도착 위치에서 탐색을 종료하면 된다. 그런데 이 문제는 시작 위치와 도착 위치가 불분명하다. 어떻게 시작해야 할까? 문제에서 제시되어 있는 .. 더보기 이전 1 다음
