BFS 썸네일형 리스트형 [수학&그래프이론] 제1회 곰곰컵 H번, 곰곰이의 심부름 문제에서 나오는 최단경로로 힌트를 얻을 수 있다. 일단 최단 경로를 구해야 한다. 최단 경로를 구하는 방법도 여러가지지만, 일단 벨만 포드로 구해볼 수도 있을 것 같은데, 벨만포드의 시간복잡도는 O(VE)이기 때문에 현 문제에서는 사용이 불가능할 것으로 보인다. 특별히 간선에 가중치도 없는 것으로 보았을 때 그냥 BFS로 진행해도 될 것 같다. 생각해야 할 부분은 최단 거리를 시작에서 목적지 까지 구하는 것이 아니라, 시작에서 심부름까지 그리고 심부름에서 목적지 까지 따로 구해야 한다는 것이다. 이걸로 한고비 넘겼고, 다음은 경로가 구해지면 어떻게 순서쌍의 갯수를 구하느냐이다. 여기서 수학의 개념이 들어가는데, 처음으로 생각해야 할 점은 이 그래프는 N개의 정점과 N-1개의 간선으로 이루어진 그래프로써,.. 더보기 [BFS]BJ_2146, 다리 만들기 0 또는 1로 이루어진 100 x 100 배열에 대해서 0을 1로 채워가면서 연결되는 최소길이를 구하는 문제이다. 어떻게 접근해야 할까? 일단 격자 형태로 좌/우/상/하를 탐색하는 문제의 경우에는 BFS부터 검토해 보는 것이 좋다. 보통의 BFS 문제가 격자를 바탕으로 이루어지기 때문이다. 이 문제도 확장 형태를 보면 BFS로 풀리는 문제라는 것은 어렵지 않게 유추할 수 있다. 다만, 어려운 점은 시작위치와 도착 위치를 어떻게 잡느냐이다. 시작 위치를 어디로 잡아야 할까? 문제에서 시작 위치와 도착 위치가 정해지는 경우는 시작위치를 queue에 넣고 탐색을 진행하되 도착 위치에서 탐색을 종료하면 된다. 그런데 이 문제는 시작 위치와 도착 위치가 불분명하다. 어떻게 시작해야 할까? 문제에서 제시되어 있는 .. 더보기 이전 1 다음
