[D3] SWEA 22683번 나무 베기 C++ 다익스트라, 최단 경로

 

리뷰

 

백준의 벽부수고 이동하기 시리즈와 유사한 문제였다.

SW Expert Academy

 

 

전역 변수

• tc, n, k : 테스크 케이스의 개수 tc, 각 테케당 한 변의 개수 n, 각 테케당 나무를 벨 수 있는 횟수 k
• sx, sy, ex, ey : 각 테스트 케이스당 시작 및 도착 지점의 x, y좌표
• lst : 문자열로 이루어진 맵 정보, 최대 10 * 10의 크기이다.
• dx, dy : 상하좌우 이동시 사용할 방향 배열, 상우하좌 순으로 인덱싱이 되어 있다.
• Pos : 탐색을 할때 현재 정보에 대한 정보를 담을 구조체, 현재 위치, 방향, 자른 나무의 개수, 시간 정보가 있다. 우선순위 큐를 사용해 주어야 하기 때문에 시간 기준 오름차순 정렬 함수를 포함한다.

 

함수

1. input

void input()

 

1. 각 테스트 케이스마다 변수와 맵 정보를 입력 받을 함수
2. 맵을 입력 받을때 X인 경우 시작 좌표 정보와 Y인 경우 도착 좌표 정보를 초기화 해준다.

 

2. solution

int solution()

 

1. 다익스트라를 통해 시작 지점에서 출발하여 도착 지점까지의 최단 거리를 구하는 함수
2. 시작x, y좌표와, 현재 바라보고 있는 방향, 나무를 자른 횟수, 시간을 0인 상태로 pq에 추가한다.
3. 거리 정보를 나타낼 3차원 벡터 dist를 k + 1 * n * n크기로, 매우 큰 값으로 초기화 해준다.
4. dist의 첫번째 크기는 나무를 벤 개수이고, 이후는 2차원 좌표이다.
5. 이후 다익스트라 탐색을 시작하고, 나무를 만나면 벨 수 있다면 벤 나무의 개수를 올려준다.
6. 만약 더 이상 벨 수 없다면 해당 탐색은 멈춰주면 된다.
7. 최종적으로 모든 나무를 벤 갯수를 탐색하며 도착 위치까지의 거리의 최소값을 구해준다.
8. 만약 최소값이 초깃값이라면 도착하지 못한 것이므로 -1을, 아니라면 최단 거리를 리턴해 준다.

 

문제풀이

1. 테스트케이스의 수를 입력받아준 뒤 각 테스트케이스를 반복하여 순회해 준다.
2. input함수를 통해 맵 정보와 한 변의 크기 n과 나무를 벨 수 있는 횟수 k, 시작과 목표 좌표를 입력 받아준다.
3. solution함수를 통해 목적지 까지의 최단거리를 구해주고 리턴받은 값을 출력해 준다.

 

참고 사항

• RC카는 앞으로 이동, 왼쪽으로 90도 회전, 오른쪽으로 90도 회전이 가능하며, 각 명령 시 시간이 1소비된다.
• 즉 위를 보고 있는 상태에서 아래로 이동하려면 오른쪽이나 왼쪽으로 90도 회전 2번과 이동을 하느라 3의 시간이 소비된다. 이 부분을 빠르게 체크해주기 위해 구조체에 현재 방향 정보가 있는 것이다.
• 다익스트라에 사용할 거리 정보는 나무를 제거한 케이스를 모두 알고 있어야 정확한 답이 나온다.

 

정답 코드

#include<iostream>
#include<queue>

using namespace std;
int tc, n, k, sx, sy, ex, ey;
string lst[10];

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };

struct Pos {
    int x, y, dir, cut, time;
    bool operator<(const Pos& other) const {
        return time > other.time;
    }
};

void input() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> lst[i];
        for (int j = 0; j < n; j++) {
            if (lst[i][j] == 'X') sx = i, sy = j;
            else if (lst[i][j] == 'Y') ex = i, ey = j;
        }
    }
}

int solution() {
    priority_queue<Pos> pq;
    pq.push({ sx, sy, 0, 0, 0 });
    vector<vector<vector<int>>> dist(k + 1, vector<vector<int>>(n, vector<int>(n, 1e9)));
    dist[0][sx][sy] = 0;

    while (!pq.empty()) {
        Pos pos = pq.top(); pq.pop();
        int cx = pos.x, cy = pos.y, cd = pos.dir, cc = pos.cut, ct = pos.time;
        if (dist[cc][cx][cy] != ct) continue;
        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i], ny = cy + dy[i], nc = cc, nt = ct + 1;
            if (abs(cd - i) == 3) nt += 1;
            else nt += abs(cd - i);
            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                if (lst[nx][ny] == 'T') {
                    if (nc >= k) continue;
                    else nc++;
                }
                if (dist[nc][nx][ny] > nt) {
                    dist[nc][nx][ny] = nt;
                    pq.push({ nx, ny, i, nc, nt });
                }
            }
        }
    }
    int ans = 1e9;
    for (int i = 0; i <= k; i++) ans = min(ans, dist[i][ex][ey]);
    if (ans == 1e9) return -1;
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        input();
        cout << "#" << t << " " << solution() << "\n";
    }
}