[정올] 등산로 찾기

http://jungol.co.kr/bbs/board.php?bo_table=pbank&code=1111&sca=4070 

JUNGOL

bfs를 이용하는 문제입니다.

 

산이 있는데, 가장 외곽 둘레에서 출발하여 목적지 까지 도착해야 합니다. 이 때, 출발높이와 도착 높이에 따라 사용된 힘의 크기가 달라질 때, 가장 경제적으로 올라갈 때 드는 힘을 구해야 합니다.

 

<Solution>

총 두가지 정도 생각을 해 볼 수 있습니다.

1. 가장 외곽 둘레부터 출발하는 방식 2. 산의 정상에서 출바하는 방식

총 이렇게 두 지점을 출발 위치로 잡을 수 있습니다. 저의 경우 가장 외곽부터 출발하도록 하였는데, 이렇게 할 때도 외곽의 한 지점만 넣어주고 자동으로 확산될 수 있도록 가중치를 주는 더 나은 방식을 이용할 수 도 있습니다.

 

실제 코드 구현은 아래와 같습니다. 

#include <iostream>
#include <queue>
#include <utility>
 
using namespace std;
 
#define MAXN (102)
int N;//산크기
int eh, ew;//목적지 위치 세로, 가로
int map[MAXN][MAXN];
int visited[MAXN][MAXN];
 
int d_row[] = {0, 0, 1, -1};
int d_col[] = {1, -1, 0, 0};
 
void InputData(){
    cin >> N;
    cin >> eh >> ew;
    for (int h=1; h<=N; h++){
        for (int w=1; w<=N; w++){
            cin >> map[h][w];
            visited[h][w] = 1<<30;
        }
    }
}
 
 
int solution(){
    queue <pair<int,int> > q;
    for(int i=0; i<=N+1; i++){
        q.push(pair<int,int>(0,i));
        q.push(pair<int,int>(N+1,i));
    }
     
    for(int i = 1; i<=N; i++){
        q.push(pair<int,int>(i,0));
        q.push(pair<int,int>(i,N+1));
    }
 
    while(!q.empty()){
        pair<int,int> cur = q.front(); q.pop();
 
        for(int i = 0; i<4; i++){
 
            int new_r = cur.first+d_row[i];
            int new_c = cur.second+d_col[i];
 
            // 배열 내부인지 check
            if(!(0<=new_r && new_r <=N+1 && 0<=new_c && new_c <= N+1)) continue;
 
            // 새 비용 계산
            int new_cost = visited[cur.first][cur.second];
 
            if(map[cur.first][cur.second] == map[new_r][new_c]) new_cost += 0;
            else if(map[cur.first][cur.second] > map[new_r][new_c]) new_cost+= (map[cur.first][cur.second]-map[new_r][new_c]);
            else{
                int tmp = map[new_r][new_c] - map[cur.first][cur.second];
                new_cost += tmp*tmp;
            }
            // 더 나은지 확인
            if(new_cost < visited[new_r][new_c]){
                // 더 나은 경우라면
                visited[new_r][new_c] = new_cost;
                q.push(pair<int,int>(new_r,new_c));
            }
        }
    }
    return visited[eh][ew];
}
 
 
 
int main(){
    int ans = -1;
    InputData();//입력 받는 부분
 
    //여기서부터 작성
    ans = solution();
 
    cout << ans << endl;//출력하는 부분
    return 0;
}