BFS
BFS
- 최단 경로 전략
- 복잡도: O(V + E) 모든 정점을 한번씩 방문하며 정점을 방문할 때마다 인접한 모든 간선 검사
자동차 경주
https://www.acmicpc.net/problem/2611
다익스트라에서 큐의 우선순위를 “가중치가 높은 노드”로 바꾸면 된다. 경로 출력은 큐에 넣는 작업을 할때마다 그 때의 이전 노드를 따로 저장 (즉, 어디서부터 왔는 가를 저장)하여 마지막엔 시작 노드로부터 그 역순으로 따라올라가면 경로를 얻을 수 있다.
for (V next : adj.get(curr.to)) {
if (dist[curr.to] + next.w > dist[next.to]) {
dist[next.to] = dist[curr.to] + next.w;
q.add(new V(next.to, dist[next.to]));
trace[next.to] = curr.to;
}
}
//경로 출력은 stack을 쓰는게 깔끔
System.out.println(dist[1]);
// LIFO
Stack<Integer> st = new Stack<Integer>();
st.push(1);
st.push(trace[1]);
int last = trace[1];
while (last != 1) {
last = trace[last];
st.push(last);
}
while (!st.isEmpty()) {
System.out.print(st.pop() + " ");
}
// 혹은 재귀를 이용
static void printPath(int last) {
if (trace[last] == 1) {
System.out.print(1 + " " + last);
return;
}
printPath(trace[last]);
System.out.print(" "+ last);
}native dfs
static void dfs(int curr, ArrayList
return;
}
for (V next : adj.get(curr)) {
dfs(next.to, path, max + next.w);
// path.remove(path.size()-1); 여기서 remove할 경우 최종적으로 curr 에 대한 remove 도 필요하다
}
// context 가 끝난 시점에 remove하는게 간결
path.remove(path.size() - 1); }
Dijkstra
한 정점에서 모든 정점의 최단거리 방향그래프
무향 BFS 최단거리와 비슷하나 priority queue를 이용
PriorityQueue<Edge> que = new PriorityQueue<>();
visited[start] = true;
dist[start] = 0; // INF로 초기화
que.add(new Edge(start, 0));
while (!que.isEmpty()) {
int cur_index = que.peek().index;
int cur_w = que.peek().weight;
que.poll();
if (dist[cur_index] < cur_w) {
continue;
}
for (Edge edg: list.get(cur_index)) {
int next_index = edg.index;
int next_weight = edg.weight;
if (next_index == cur_index) {
continue;
}
if (!visited[next_index] || dist[cur_index] + next_weight < dist[next_index]) {
dist[next_index] = dist[cur_index] + next_weight;
visited[next_index] = true;
que.add(new Edge(next_index, dist[next_index]));
}
}
}
for (int i = 1; i <= V; i++) {
if (dist[i] == Integer.MAX_VALUE) {
System.out.println("INF");
} else {
System.out.println(dist[i]);
}
}9-퍼즐
- 복잡도 정점의 수: 9! 탐색 분기수 b: 4방향이나 이전정점돌아가는길이나 중복경우 존재해 약 3이하의 어느값 최단거리를 d 라고 한다면 O(b^d)
b=2, d = 20 이라하면 2^20 = 최소 백만 2^10 = 1024 2^20 = 100만 2^32 = 42억
양방향 탐색이면 O(b^(d/2)) 복잡도가 나온다
- 퍼즐의 상태를 어떻게 나타내나? – 1. vector를 이용해 각 위치의 순서대로 값을 넣어둔다 – 2. bit? 각각의 상태를 bit로 표현한다. 최대 크기가 8 (1000) 이므로 각 상태는 bit 4개필요, 총 9개이므로 36bit (4 * 9) 필요하므로 64bit 정수형으로 표현이 가능하다.