목록Algorithms/BFS (12)
혼종 꼬지마루
BFS에 올리긴 했지만, 다익스트라 문제 벽 부수고 이동하기와 같은 문제인 듯 하지만, 이동거리가 최소가 아닌, 벽을 최소로 부수는 것 1. visit배열을 선언해서 최대값으로 초기화 2. BFS탐색을 하면서 벽이 있는 것을 dis로 계산해서 이동위치가 최소가 되는 지점만 큐에 담는다 3. 도착위치에 있는 visit을 출력 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #define MX 102using namespace std; struct ALGO { int x, y;}q[MX*MX*MX]; int map[MX][MX], visit[MX][MX];int dx[] = { ..
이 문제는 BFS에 넣어두긴 했지만 트리 구조를 인접행렬로 만드는게 더 중요한 문제 1. 입력되는 간선의 정보와 가중치를 map과 w배열을 만들어 저장 2. 트리의 마지막 노드에서 출발하는 것이 가장 큰 값을 나타내게 되기 때문에 map에서 갈 수 있는 정점의 수가 1개인 곳만 찾아서 bfs 탐색 결과적으로는 맞았지만 1832ms나 걸렸기 때문에 효율적이라고는 생각되지 않는코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #define MX 10002using namespace std; int map[MX][1000], w[MX][1000], q[MX];int N, dab; void bfs(i..