BFS
✔️ BFS에서 방문 체크의 상태가 2차원 배열인 경우
map<vector<vector<int>>, int>를 사용해 해시로 상태를 관리할 경우 메모리 초과와 시간 초과이다.
해결 아이디어는 2차원 배열 상태를 문자열로 변환하여 unordered_map<string, int>의 키 값으로 사용해 방문 체크를 하면 된다.
관련문제
✔️ 방문 제한 구역(정점(\(X\), \(Y\))을 기준으로 거리 \(D\) 이하의 정점들의 영역)이 있는 경우
다익스트라 알고리즘을 응용해 방문 제한 구역을 체크할 수 있다.
아이디어는 인접한 정점까지 더 늦게 방문 할 수 있도록 거리 배열을 최신화하여 최대한 방문하지 못하는 구역을 넓히는 것이다.
while (!pq.empty()) {
auto [d, x, y] = pq.top();
pq.pop();
if (d < dist[y][x] || d <= 0) continue;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (inside(nx, ny) && dist[ny][nx] < d - 1) {
dist[ny][nx] = d - 1;
pq.emplace(d - 1, nx, ny);
}
}
}
만약 방문 제한 구역의 개수가 적을 경우 방문 제한 구역의 테두리만 체크해 BFS 수행시 방문하지 않는 아이디어도 있다.
for (int i = 0; i < k; i++) {
int r, c, d;
cin >> r >> c >> d;
for (int ddx = 0; ddx <= d; ddx++) {
int ddy = d - ddx;
for (int nx : {c + ddx, c - ddx}) {
for (int ny : {r + ddy, r - ddy}) {
if (inside(nx, ny)) board[ny][nx] = 1; // 방문하지 못한다.
}
}
}
}
관련문제
Dijkstra
✔️ 출발 정점에서부터 중간에 P개의 정점을 모두 거친 후 도착 정점까지의 최단거리
중간에 거쳐야하는 P개의 정점들 사이의 \(P \times P\) 거리 배열을 만든다. 이제 주어진 문제를 출발 정점 -> a -> ... -> b -> 도착 정점까지의 최단 거리 문제로 바꾸고, a -> ... -> b 의 거리를 TSP로 구하면 된다.
관련문제
댓글