T5 격자 경로
메모리 제한: 256 Mb | 시간 제한: 1000 ms
문제 설명
n × m개의 격자로 이루어진 지도가 주어진다. 각 격자에는 지형 정보가 있다:
- 일부 격자는 벽(#)이며, 통과할 수 없다.
- 일부 격자는 길(.)이며, 통과할 수 있다.
좌상단 격자에서 시작하여 우하단 격자까지 최단 거리로 도착하는 경우의 수를 구해야 한다. 이동 중에는 벽 격자로 진입할 수 없으며, 시작점과 도착점은 벽이 아니다. 이동은 상하좌우 인접한 격자로만 가능하다.
결과 값이 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.
입력 형식
첫 번째 줄: 정수 n과 m
두 번째 줄부터 n+1줄: 각 줄에 m개의 문자로 지형 정보
출력 형식
최단 경로의 경우의 수를 1,000,000,007로 나눈 나머지를 출력
데이터 범위
- 30점: 1 ≤ n, m ≤ 4
- 60점: 1 ≤ n, m ≤ 10
- 100점: 1 ≤ n, m ≤ 1000
예제
입력:
3 3 ... .#. ...
출력:
2
해석
이 문제는 n×m 격자에서 '#'은 장애물, '.'은 통로이다. 일반적인 최단 경로 문제와 달리 여기서는 최단 경로의 개수를 구하는 것이 핵심이다.
접근법 1: BFS로 최단 거리 계산 + DFS로 경로 개수 세기 (70점)
DFS에서 사용할 수 있는 가지치기는 일반적인 최적화 가지치기와 다르다. 일반적인 문제에서는 동일한 깊이에 도달하면剪掉하지만, 이 문제는 경로의 개수를 구하는 것이므로 그런 가지치기를 사용할 수 없다. 구조체에는 좌표(x, y)와 현재까지의 걸음 수(pos)가 포함된다.
#include
using namespace std;
const long long MOD = 1000000007LL;
int n, m;
int dist[1010][1010];
int moveX[4] = {0, 1, 0, -1};
int moveY[4] = {1, 0, -1, 0};
int minSteps, pathCount;
char board[1010][1010];
struct Node {
int x, y, steps;
};
Node queueArr[1000010];
int findShortestPath() {
int frontIdx = 0, backIdx = 1;
queueArr[0] = {1, 1, 0};
while (frontIdx < backIdx) {
if (queueArr[frontIdx].x == n && queueArr[frontIdx].y == m) {
return queueArr[frontIdx].steps;
}
int curX = queueArr[frontIdx].x;
int curY = queueArr[frontIdx].y;
for (int dir = 0; dir < 4; ++dir) {
int nextX = curX + moveX[dir];
int nextY = curY + moveY[dir];
if (nextX > 0 && nextX <= n && nextY > 0 && nextY <= m &&
dist[nextX][nextY] == -1 && board[nextX][nextY] == '.') {
queueArr[backIdx].x = nextX;
queueArr[backIdx].y = nextY;
queueArr[backIdx].steps = queueArr[frontIdx].steps + 1;
dist[nextX][nextIdx] = 1;
++backIdx;
}
}
++frontIdx;
}
return -1;
}
void countPaths(int x, int y, int steps) {
if (steps >= minSteps) {
if (x == n && y == m && steps == minSteps) {
pathCount = (pathCount + 1) % MOD;
}
return;
}
dist[x][y] = steps;
for (int dir = 0; dir < 4; ++dir) {
int nextX = x + moveX[dir];
int nextY = y + moveY[dir];
if (nextX > 0 && nextX <= n && nextY > 0 && nextY <= m &&
(dist[nextX][nextY] == -1 || dist[nextX][nextY] >= steps + 1) &&
board[nextX][nextY] == '.') {
countPaths(nextX, nextY, steps + 1);
}
}
}
int main() {
memset(dist, -1, sizeof(dist));
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> board[i][j];
}
}
minSteps = findShortestPath();
memset(dist, -1, sizeof(dist));
countPaths(1, 1, 0);
cout << pathCount << endl;
return 0;
} 이 코드는 시간 초과로 3개의 테스트 케이스에서 실패한다.
접근법 2: BFS 기반 경로 탐색 (STL 큐 사용) (70점)
10,000,000 크기의 배열을 사용하면 메모리 초과가 발생할 수 있다. STL 큐를 사용하는 방식으로 구현해보았지만, 여전히 시간 초과가 발생한다. 본질적으로 모든 경로를枚举하면서 개수를 세는 방식이므로, 10억 이상의 경우의 수가 발생할 수 있어 시간 초과가 불가피하다. 가지치기 방법은 앞의 방법과 동일하다.
#include
using namespace std;
const long long MOD = 1000000007LL;
int n, m;
int visited[1010][1010];
int dirX[4] = {0, 1, 0, -1};
int dirY[4] = {1, 0, -1, 0};
int shortestDist = LLONG_MAX;
int totalPaths;
char grid[1010][1010];
struct Position {
int x, y, distance;
};
queue<Position> q;
void bfsSearch() {
q.push({1, 1, 0});
while (!q.empty()) {
Position current = q.front();
if (current.x == n && current.y == m && current.distance <= shortestDist) {
shortestDist = current.distance;
totalPaths = (totalPaths + 1) % MOD;
}
if (current.distance < shortestDist) {
for (int d = 0; d < 4; ++d) {
int nx = current.x + dirX[d];
int ny = current.y + dirY[d];
if (nx > 0 && nx <= n && ny > 0 && ny <= m &&
(visited[nx][ny] == -1 || visited[nx][ny] == current.distance + 1) &&
grid[nx][ny] == '.') {
q.push({nx, ny, current.distance + 1});
visited[nx][ny] = q.back().distance;
}
}
}
q.pop();
}
}
int main() {
memset(visited, -1, sizeof(visited));
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> grid[i][j];
}
}
bfsSearch();
cout << totalPaths << endl;
return 0;
} 참고: Dev-C++ 5.5.2에서 큐 삽입 관련 경고가 발생할 수 있지만, 채점 사이트에서는 정상적으로 통과한다.
접근법 3: 개선된 BFS 알고리즘 (정답)
BFS의 기본 원리로 인해 더 많은 이력이 필요한 상태는 항상 더 적은 이력 이후에 처리된다. 따라서 동일한 격자를 두 번째로 방문할 때 첫 번째 상태는 아직 큐에서 나오지 않았으므로 두 상태를 하나로 합칠 수 있다.
구조체에 각 상태의 경로 개수(step)를 저장하는 필드를 추가한다. 동일한 격자를 다시 방문했을 때 두 경로 개수를 합쳐서 하나의 상태로 관리한다. 이때 가지치기 규칙은 다음과 같이 세 가지 경우로 나뉜다:
- 처음 방문하는 경우: 새 상태를 생성
- 동일한 거리로 방문하는 경우: 경로 개수 합산
- 더 큰 거리로 방문하는 경우: 무시
#include
using namespace std;
const long long MOD = 1000000007LL;
int n, m;
int level[1010][1010];
int dirX[4] = {0, 1, 0, -1};
int dirY[4] = {1, 0, -1, 0};
int minDistance = LLONG_MAX;
int answer;
int queueIndex[1010][1010];
char board[1010][1010];
struct State {
int x, y, dist, paths;
};
State stateArray[1000010];
void optimizedBfs() {
int front = 0, rear = 1;
stateArray[0] = {1, 1, 0, 1};
while (front < rear) {
State current = stateArray[front];
if (current.x == n && current.y == m && current.dist <= minDistance) {
minDistance = current.dist;
answer = (answer + current.paths) % MOD;
}
if (current.dist < minDistance) {
for (int d = 0; d < 4; ++d) {
int nx = current.x + dirX[d];
int ny = current.y + dirY[d];
if (nx > 0 && nx <= n && ny > 0 && ny <= m &&
(level[nx][ny] == -1 || level[nx][ny] == current.dist + 1) &&
board[nx][ny] == '.') {
if (level[nx][ny] == current.dist + 1) {
// 같은 거리의 상태를 합침
stateArray[queueIndex[nx][ny]].paths =
(stateArray[queueIndex[nx][ny]].paths + current.paths) % MOD;
} else {
// 처음 방문하는 경우
queueIndex[nx][ny] = rear;
stateArray[rear] = {nx, ny, current.dist + 1, current.paths};
level[nx][ny] = stateArray[rear].dist;
++rear;
}
}
}
}
++front;
}
}
int main() {
memset(level, -1, sizeof(level));
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> board[i][j];
}
}
optimizedBfs();
cout << answer << endl;
return 0;
} 이 최적화된 BFS 알고리즘은 상태의 중복을 효과적으로 처리하여 모든 테스트 케이스를 통과할 수 있다.