문제 이해 단계
입력으로 2차원 맵과, 지나갈 수 없는 장애물(물 웅덩이)이 0~10개 사이로 주어진다.
이때 집과 학교의 위치는 각각 (1,1) (m, n) 위치에 고정이다.
움직일 수 있는 방법은 오른쪽/아래로 움직이는 방법밖에 없을 때,
최단경로로 집에서 학교로 갈 수 있는 경로의 수를 구하는 문제이다.
문제 접근 단계
일단 출발지에서 목적지까지 경로를 구해야 하고, 맵과 장애물이 주어졌다.
높은 확률로 그래프 탐색 문제로 해결하는 것으로 보인다.
일단 움직일 수 있는 조건을 보면 오른쪽과 아래로밖에 이동하지 못한다.
그리고 찾아야 하는 것은 최단경로의 개수이다.
그렇다면 해당 경로가 최단경로인지 아닌지 어떻게 판단할 수 있을까?
사실 판단할 필요 없다. 왜냐하면 오른쪽과 아래로만 움직일 수 있다면,
집에서 학교까지 도달할 수 있는 모든 경로가 최단거리이다.
이유는 아래 그림과 같다.
가로로 움직이는 것을 파란색, 세로로 움직이는 것을 빨간색으로 표시한다면,
구불구불하게 움직이는 것과 파란색으로 쭉 움직인 후
빨간색으로 쭉 움직인 것은 거리가 같다.
이는 왼쪽과 위로 가는 것이 목적지에서 멀어지는 것이기 때문이다.
즉, 목적지에서 멀어 저는 행위 자체를 하지 않기 때문에
학교에 도달하는 모든 경로는 최단경로일 수밖에 없다.
경로 개수 구하기
경로의 수를 구하는 방법에서 일단 기본은 그래프 탐색을 사용하였다.
그중에서 하나씩 학교에 도달할 수 있는지 체크해야 하기 때문에
깊이우선탐색(DFS)이 더 어울릴 것이라고 생각했다.
이제 경로의 개수들을 어떻게 구할 것이냐는 것이다.
모든 경로를 집에서 학교까지 끝까지 DFS를 진행해서 이 결과를 맵에 저장할까?
이는 딱 봐도 시간초과가 날 것 같다. 뭔가 다른 방법이 필요하다.
그래서 각 경로마다 횟수를 저장해 둘 것이다.
예를 들어 map [i][j] = 2라는 뜻은 (i, j) 위치에
현재 (학교로 가는 것이 가능한) 진행된 경로가
이 위치를 2번 밟았다는 것을 의미한다.
즉, 이 위치에서 학교로 도달할 수 있는 방법은 2가지라는 뜻이다.
이러한 방식으로 각각의 위치에 경로 정보를 저장하여 갱신하는 방법으로 횟수를 구한다.
여기서 메모라이징 기법을 통해 이미 횟수가 저장되어 있는 곳은,
더 이상 DFS를 진행할 필요가 없으므로 바로 그 값을 리턴해준다.
이 점을 보아하니 이 문제는 DP도 섞여있는 것 같다.
밑에서 로직적으로 한번 그려보겠다.
우선 왼쪽과 같이 각 위치를 0으로 초기화해 준다.
웅덩이는 -1로 해서 갈 수 없게 한다.
이후 DFS를 진행하는데, 각 이동하는 위치에 있는 값을
이동하기 전에 있는 값과 동일하게 만들어준다.
DFS에 의해 오른쪽으로 쭉~ 갔다가 그다음 아래로 쭉~ 간다.
그러다 보면 목적지인 학교에 도달한다.
학교에 도달한 것을 확인하면
갈림길이 나오기 전까지 지나왔던 경로의 값을 +1을 하여 뒤로 간다.
그 뒤 갈림길이 나오면 다시 DFS를 진행한다.
왼쪽 그림처럼 이번에는 아래로 움직인 후 다시 오른쪽으로 이동하려고 하는데,
이미 그 위치의 값은 존재한다.
그런 경우에는 (자신의 값 + 그 위치의 값)을 해서 자신의 값으로 갱신해 준다.
그 후 다시 DFS를 진행해 준다.
위에서 했던 순서에 따라 다시 한번 아래로 이동 후,
학교에 도달한 것을 확인, 값을 +1 해준다.
이제 끝에 도달했으니 자신의 경로 값을 반환해 준다.
재귀함수를 호출했던 함수는 (자신의 값 + 리턴 받은 값)으로 갱신해 준다.
이렇게 되면 집에서 오른쪽 방향으로 갔을 때의 경로의 수 확인은 끝났다.
오른쪽으로 갔을 때 가능한 경로는 총 3개이다.
이제 아랫 방향으로 이동했을 때를 가정해 보자.
일단 물웅덩이 부분은 이동할 수 없으니 그대로 지나가고, 노란색 경로로 진행한다.
진행하다 보면 이미 값이 존재하는 초록색 경로를 만나게 된다.
그러면 위에서 했던 것처럼 (그 위치값 + 현재 값)으로 갱신하고 재귀함수를 종료한다.
이렇게 되면 모든 탐색이 끝나고,
(1,1)을 확인해 보면 정상적으로 가능한 경로 4가 나오는 것을 확인할 수 있다.
이제 위의 로직을 알고리즘으로 구현하면 된다.
문제 구현 단계
int map[101][101]= {0,};
int dfs(int x, int y ,int endX, int endY){
// 오른쪽, 아래 움직임
int dx[] = {0,1};
int dy[] = {1,0};
for(int i = 0; i < 2; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 1 || ny < 1 || nx > endX || ny > endY || map[nx][ny] == -1) continue;
// 다음 이동 경로가 학교인 경우 현재위치 + 1 반환
if(nx == endX && ny == endY) return map[x][y] += 1;
// 다음 이동 경로에 이미 값이 존재할 때(이미 지나간 경로)
if(map[nx][ny] > 0) {
map[x][y] += map[nx][ny]; // 현재 위치 값 + 다음 이동 경로 값
map[x][y] %= 1000000007;
continue;
}
// 호출했던 dfs 함수들의 값(경로 수)를 반환받아 이를 현재 위치값에 더함
map[x][y] += dfs(nx,ny,endX,endY);
map[x][y] %= 1000000007;
}
// 현재 위치값 반환
return map[x][y];
}위에서 설명했던 그림을 구현한 코드이다.
인자로 x위치, y위치 그리고 가로, 세로(m, n)를 받는다.
기본적인 DFS와 형식은 같다.
다른 점은 해당 DFS에서는
방문을 체크하는 visitd 배열이 존재하지 않는데,
이유는 오른쪽과 아래로만 움직이기 때문에
어차피 한 탐색에서 이전에 갔던 곳은 올 수 없기 때문이다.
m과 n을 벗어나거나, x와 y가 0보다 작아지는 경로는 무시한다.
또한 다음 경로가 물웅덩이인 경우에도 무시한다.
만약 다음 경로가 (m, n) -> 학교인 경우,
현재 위치+1을 반환하고 함수를 종료한다.
맵 배열 안에 값이 0보다 크다면 이미 지나갔던 경로로 판단하고,
그 경로 값을 현재 경로에 더해주고 다음 경로를 탐색한다.
결국 현재 경로에는 해당 경로로 dfs를 했을 때의 결과가 저장됨으로,
결과적으로는 그 위치에서 출발했을 때의 모든 가능한 경로의 수가 나오게 된다.
이제 아래에 전체 코드를 올리고 마치겠다.
#include <string>
#include <vector>
using namespace std;
int map[101][101]= {0,};
int dfs(int x, int y ,int endX, int endY){
// 오른쪽, 아래 움직임
int dx[] = {0,1};
int dy[] = {1,0};
for(int i = 0; i < 2; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 1 || ny < 1 || nx > endX || ny > endY || map[nx][ny] == -1) continue;
// 다음 이동 경로가 학교인 경우 현재위치 + 1 반환
if(nx == endX && ny == endY) return map[x][y] += 1;
// 다음 이동 경로에 이미 값이 존재할 때(이미 지나간 경로)
if(map[nx][ny] > 0) {
map[x][y] += map[nx][ny]; // 현재 위치 값 + 다음 이동 경로 값
map[x][y] %= 1000000007;
continue;
}
// 호출했던 dfs 함수들의 값(경로 수)를 반환받아 이를 현재 위치값에 더함
map[x][y] += dfs(nx,ny,endX,endY);
map[x][y] %= 1000000007;
}
// 현재 위치값 반환
return map[x][y];
}
int solution(int m, int n, vector<vector<int>> puddles) {
int answer = 0;
// 물 웅덩이 추가
for(int i = 0; i < puddles.size(); i++){
if(puddles[i].empty()) continue;
map[puddles[i][1]][puddles[i][0]] = -1;
}
// 집에서부터 dfs 시작
answer = dfs(1,1,n,m);
return answer;
}
시행착오
처음에는 해당 문제를 빨리 풀 줄 알았는데, 풀이를 아예 잘못 접근했다.
그리고 답을 산출하는 방식 또한 잘못돼서 계속 틀린 알고리즘을 짜고 있었다.
원래는 해당 방식으로 말고 다른 방식으로 만들다가
불현듯 이 방법이 떠올라서 테스트하던 코드를 싹 다 지우고 다시 작성했다.
문제를 테스트할 때 좀 더 신중히 테스트하는 버릇을 길러야겠다.