백준 16928 뱀과 사다리 게임 c++ [컴공과고씨]

https://www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

 

이 문제 같은 경우는 탐색 BFS 알고리즘을 이용하면 쉽게 구현이 가능하다.

보드판 100칸 중에 사다리 혹은 뱀이 있을 경우 도착 지점을 적어두고 나머지는 0으로 해서 특수한 경우와 일반 경우를 구별해준다. bfs를 구현할 때는 큐에 좌표와 주사위를 굴릴 때마다 카운트 하는 변수를 넣어준다.

주사위가 1일때 부터 6일때까지 반복해주고 현재 좌표에 더해서 다음 좌표를 만든다.

다음 좌표가 100일 경우 카운트에 +1해서 출력해준다.

만약 100보다 작을 경우 먼저 다음 좌표에 사다리 혹은 뱀인지 확인해서 0이 아닌 경우 적혀있는 값으로 좌표를 이동해준다. 

그 후 다음 좌표가 이전에 방문되어지지 않았다면 큐에 넣어주고 방문 처리를 해준다.

방문한 좌표를 다시 방문할 필요가 없는 이유는 먼저 방문한 애가 있다면 그 뒤에 온 좌표는 무조건 그 앞 좌표보다 느리고 중복이기 때문에 다시 방문할 필요가 없다.

 

전체 코드

#include <iostream>
#include <queue>
using namespace std;
int map[102] = {0};
bool visit[102] = {0};
 
void game(int x, int c){
    queue<pair<int, int>> q;
    q.push(make_pair(x, c));
    while(!q.empty()){
        int loc = q.front().first; // 현재 좌표
        int cnt = q.front().second; // 카운트
        q.pop();
 
        for (int i = 1; i <= 6;i++){
            int nx = loc + i; // 다음 좌표
            if(nx == 100){
                cout << cnt+1; // 도착했으면 출력
                return;
            }
            else if(nx < 100){ // 100보다 작은 좌표라면 
                while(map[nx] != 0){ // 사다리 혹은 뱀인지 확인
                    nx = map[nx]; // 점프한 자리로 이동
                }
                if(!visit[nx]){ // 처음 방문한 좌표일때
                    q.push(make_pair(nx, cnt + 1)); // 큐에 넣어줌
                    visit[nx] = true; // 방문처리
                }
                
            }
        }
    }
}
 
int main(){
    int n, m, t1, t2;
    
    cin >> n >> m;
    for (int i = 0; i < n;i++){
        cin >> t1 >> t2; 
        map[t1] = t2; // 사다리 저장
    }
    for (int i = 0; i < m;i++){
        cin >> t1 >> t2;
        map[t1] = t2; // 뱀 저장
    }
    game(1, 0);
    return 0;
}

체감 난이도	걸린 시간	참고	사용 알고리즘
중	38min	x	BFS

후기 : 처음에 백트랙킹으로 잘못접근해서 시간초과가 생겨서 소요시간이 조금 걸렸다.