[해커랭크] Snakes and Ladders: The Quickest Way Up (C++)

문제 링크: www.hackerrank.com/challenges/the-quickest-way-up/problem

Snakes and Ladders: The Quickest Way Up | HackerRank

0. 유사문제

- 백준의 숨바꼭질 유형

Ex. www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

1. 주의할 점

- BFS를 통해 수행하며 해당 위치에 주사위를 현재보다 적게 굴려서 방문한 적이 있다면 방문하지 않는다

 

2. 구현

- 100인 지점에 도달하지 못했을 경우를 대비하여 Result를 -1로 초기화한다

- Check[]배열을 통해 해당 위치에 도달하기까지 굴린 주사위의 최소 횟수를 저장한다

- 큐를 사용하며 BFS를 통해 1~6칸 이동한다.

- 이동할 칸의 Check[]값과 현재 CV(현재까지 굴린 주사위 횟수)+1을 비교하여 움직임 유무를 판단한다

- 다음칸으로 이동이 가능하다면, 해당 칸이 뱀의 머리부분이나 사다리의 시작부분인지 확인하며 이에 해당한다면 주사위 위치를 옮긴다(이때에도 Check[]값 비교)

- 만약 끝지점에 도달했다면, BFS의 특성상 가장 빠르게(CV값이 가장 작은) 도착했으므로 Result에 CV값을 대입하고 While문을 종료한다

#include <bits/stdc++.h>

using namespace std;
struct info{
    int loc,val;
};
info tmp;
int check[101];
// Complete the quickestWayUp function below.
int quickestWayUp(vector<vector<int>> ladders, vector<vector<int>> snakes) {
    int result=-1;
    for(int i=2;i<=100;i++)
        check[i]=987654321;
    queue<info> q;
    tmp.loc=1;
    tmp.val=0;
    q.push(tmp);
    while(!q.empty()){
        int cl = q.front().loc;
        int cv = q.front().val;
        q.pop();
        if(cl==100){
            result=cv;
            break;
        }
        for(int i=1;i<7;i++){
            int nl = cl+i;
            if(check[nl]>cv+1){
                check[nl]=cv+1;
                //사다리 타고 이동
                for(int j=0;j<ladders.size();j++){
                    int ls = ladders[j][0];
                    if(ls!=nl) continue;
                    
                    if(check[ladders[j][1]]>cv+1){
                        check[ladders[j][1]]=cv+1;
                        nl = ladders[j][1];
                        break;
                    }                  
                }
                //뱀의 머리에 먹혀서 밑으로 이동
                for(int j=0;j<snakes.size();j++){
                    int ss = snakes[j][0];
                    if(ss!=nl) continue;
                    if(check[snakes[j][1]]>cv+1){
                        check[snakes[j][1]]=cv+1;
                        nl = snakes[j][1];
                        break;
                    }
                }
                tmp.loc=nl;
                tmp.val=cv+1;
                q.push(tmp);
            }
        }
    }
    return result;
}