새롭게 풀어본 문제는 BOJ 1520 내리막길 문제 입니다~!
BOJ 1520 내리막길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.
현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.
지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.
입출력
나의 풀이
문제를 보자마자 BFS 로 풀어야 겠다고 딱 생각했다.
평소에 DFS 알고리즘은 잘 생각이 나는데 BFS는 DFS 에 비해 잘 안해보게 되고 생각도 잘 안나던터라 BFS, DFS 다 되겠지만 DFS의 시간초과도 걱정되고 BFS 연습도 할 겸 BFS 로 풀이를 시도하였다.
주어진 예제 입력을 손으로 확인해 보니 뱅글뱅글 돌게 된다거나, 중복해서 경로 수가 체크되는 경우는 없었지만 문제에 분명 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 라고 적혀 있었기 때문에 다른 테스트 케이스에서는 이런 경우가 분명 생길 수 있을 것이라 생각했다.
하지만 visited 배열을 쓰자니 한 지점에 두가지 경로로 방문할 수 있기 때문에 이는 사용할 수 없을 것 같았고,, 그럼 어떻게 접근하지..? 하면서 고민을 좀 많이 했다.
그러다가 DP를 사용하면 될 거라는 힌트를 얻었고 DP를 사용해서 2차원 vector 형 dp를 두어 각 지점까지 가능한 누적 경로수를 저장하고 최종적으로는 dp[M-1][N-1] 값을 반환하면 되겠다싶어 코드를 작성해 제출했지만 여전히 시간 초과 문제가 해결되지 않았다!
같은 문제를 푼 친구의 포스팅을 보니 BFS 적용 시 일반 큐 대신 우선순위 큐를 사용하였는데, 무조건 높은 지점부터 방문하도록 하여야 각 지점을 한번씩만 탐색한다는 걸 알게되었다!
그림으로 보면,
20이 적혀있는 [1,3] 지점엔 도달하는 방식이 두가지가 존재한다!
위쪽 32에서 바로 내려오는 방법과, 32-30-25를 거쳐 돌아오는 두가지 길이 있다.
이때 단순히 각 지점에서 4지점을 탐색해 작은 값을 갖는 지점을 queue에 넣는다면,
32에서 바로 20으로 가는 경우 dp 배열을 오른쪽과 같겠지만,
이후 32-30-25-20 코스로 탐색이 이루어지면 이미 탐색이 된 20의 dp 값이 새로 적혀지고 이에 따라 이후 탐색되게 되는 17의 dp 값 역시 갱신되게 된다.
이러한 과정에서 시간초과가 났다고 생각했고, 이를 방지하기 위해 높이 값이 높은 칸 먼저 확인할 수 있도록 우선순위 큐를 사용하였다!
또한 20에 두번째 값이 더해져 20의 dp값, dp[1][3]이 2로 수정될 때에는 [1,3] 이 큐에 다시 들어갈 필요가 없으므로 (이미 큐에 들어가 있음) dp값이 0보다 클 때에는 우선순위 큐에 넣어주는 과정을 생략하였다!
코드
#include <iostream>
#include <vector>
#include <queue>
// BOJ 1520 내리막길, BFS
using namespace std;
// 각 지점의 높이 값과 해당 좌표 값을 함께 저장, 구조체 사용
typedef struct point {
int height;
pair<int, int> coor;
point() {
height = 0;
};
point(int h, pair<int, int> c){
height = h;
coor = c;
}
} Point;
// 우선순위 큐 정렬 기준, 높이가 높은 순서대로
struct comp {
bool operator()(Point a, Point b){
return a.height < b.height;
}
};
int dy[4] = {-1, 0, 1,0};
int dx[4] = {0, 1, 0, -1};
int getPathToExit(int M, int N, vector<vector<int>> map){
vector<vector<int>> dp(M, vector<int>(N,0)); // 경로 수 기록
pair<int, int> destination = make_pair(M-1, N-1); // 목적지
priority_queue<Point, vector<Point>, comp> pq;
queue<pair<int, int>> points; // 탐색할 좌표들
pair<int, int> location; // 현재 확인하고 있는 위치
pq.push(Point (map[0][0],make_pair(0,0)));
dp[0][0] = 1;
while (!pq.empty()){
location = pq.top().coor;
pq.pop();
if (location == destination){
continue;
}
int height = map[location.first][location.second];
for (int i = 0; i < 4; ++i) { // 위쪽 칸부터 시계 방향으로 확인
int row = location.first + dy[i];
int col = location.second + dx[i];
if (row >= 0 && row < M && col >= 0 && col < N){
if (map[row][col] < height){
if (dp[row][col] == 0){ // 처음 dp값을 확인하게 될 때에만 pq.push
pq.push(Point(map[row][col], make_pair(row,col)));
}
dp[row][col] += dp[location.first][location.second];
}
}
}
}
return dp[M-1][N-1];
}
int main() {
int M, N;
cin>>M>>N;
vector<vector<int>> map(M, vector<int>(N, 0));
for (int i = 0; i < M; ++i) {
for (int j=0; j<N; j++){
cin>>map[i][j];
}
}
int answer = getPathToExit(M, N, map);
cout<<answer;
return 0;
}코드가 좀 긴 것 같아 찜찜하지만,, 암튼 풀이 완료!
