둘러쌓인 영역 찾기
문제점
경계와 인접한 영역은 어떻게 필터링할 것인가?
해결 아이디어
경계에 있는 'O'에서 BFS를 수행해 경계와 인접한 영역을 찾는다.
queue<pair<int, int>> q;
for (int y = 0; y < n; y++) {
if (board[y][0] == 'O') q.emplace(0, y);
if (board[y][m - 1] == 'O') q.emplace(m - 1, y);
}
for (int x = 0; x < m; x++) {
if (board[0][x] == 'O') q.emplace(x, 0);
if (board[n - 1][x] == 'O') q.emplace(x, n - 1);
}
// BFS 수행
관련 문제
BFS에서 방문 체크의 상태가 2차원 배열인 경우
문제점
트리(map<vector<vector>, 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; // 방문하지 못한다.
}
}
}
}관련문제
출발 정점에서부터 중간에 P개의 정점을 모두 거친 후 도착 정점까지의 최단거리
해결 아이디어
중간에 거쳐야하는 \(P\)개의 정점들 사이의 \(P \times P\) 거리 배열을 만든다. 문제를 출발 정점 → a → ... → b → 도착 정점까지의 최단 거리 문제로 바꾸고, a → ... → b 의 거리를 TSP로 구한다.
관련문제