[C++] 백준/BOJ - 16928 : 뱀과 사다리 게임

문제 이해 단계

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

16928번: 뱀과 사다리 게임

10x10 짜리 맵에 사다리와 뱀과 맵이 있다.
그리고 플레이어는 1~6까지 적혀있는 주사위로 움직인다.

목표는 1에서 100까지 움직이는 것이다.
주사위 결과가 100칸을 넘어서 움직이는 것이라면 이동할 수 없다.

사다리와 뱀은 둘 다 점프 개념으로 사다리는 뒤에서 앞으로,
뱀은 앞에서 뒤로 이동하는 개념이다.

N개의 사다리와 M개의 뱀이 주어진다.

주사위를 마음대로 조작할 수 있을 때,
주사위를 최소로 사용하여 100까지 이동시키는 횟수를 구하는 문제

 

---

문제 접근 단계

일단 이 문제의 특이한 점은 맵의 크기가 정해져 있다는 점이다.(10x10)

그리고 2차원 맵이라고 해놓고
1 ~ 100까지 라고 1차원맵으로 정보를 준다.

문제를 분석해 보자면, 언뜻 보기엔 사다리는 도움을 주고 뱀은 손해만 주는 것 같은데
뱀을 사용해서 100까지 더 빨리 가는 경우도 존재한다.

사다리 (1,20) (16,98)
뱀 (24,14)

뭐 이런 식으로 있으면, 뱀을 타고 뒤로 간 것이 이득을 준다.

여기서 느낀 점이 사다리와 뱀의 이득을 따지는 것은 무의미하다.
그래서 주목한 것이 이동 횟수의 제한성이다.

주사위로 인해 한번 이동할 때, 선택지가 6가지밖에 없다.
이를 이용해서 경우의 수를 따져본다.

10x10 배열이기도 하고, 최종 경로에 도달해서
횟수를 확인해야 하는 문제이다 보니, 백트래킹을 통해 풀려고 했다.

그런데 매 위치마다 1~6씩 이동하는 경우의 수와,
사다리와 뱀에 의해 위치가 바뀌는 경우의 수가 중복돼서 실패했다.

그래서 다음으로 사용한 방법이 최소 횟수 구하고,
탐색을 하는데 좋은 그래프 탐색 방법이었다.

BFS를 사용해서 1칸부터 6칸까지 움직이면서
각 칸에 최소 이동 거리를 저장해 둔다.

그리고 그 칸에 사다리나 뱀이 있다면
그 칸과 연결된 칸을 큐에 넣어 워프를 시킨다.

큐에 담아지는 순서를 설명하는 그림

왼쪽이 맵이고, 오른쪽이 큐이다.

이런 식으로 그냥 주사위 이동에는 다음 번째 번호를 넣고,
뱀이나 사다리는 연결된 번호를 큐에 넣는다.

이런 식으로 각 칸에는 최소 이동 횟수 정보를 저장시키고,
BFS를 통해 맵 전체를 탐색함으로써 답을 구했다.

자세한 것은 코드로 설명한다.

 

---

문제 구현 단계

int map[101]= {0,};
int visited[101]; // 방문 체크


void bfs(int sx){
    queue<int> q;
    visited[sx] = 0; // 출발 위치
    q.push(sx); // 1 큐에 넣음

    while(!q.empty()){
        int x = q.front();
        q.pop();
        if(x > 100) continue; // 100이 넘는 값은 넘김
        for(int i = 1; i <= 6; i++){
            int nx;
            // 100 이하 && 사다리 또는 뱀일때 
            if(x+i <= 100 && map[x+i]) nx = map[x+i]; // 연결된 번호를 nx로
            else nx = x+i; // 그게 아니면 다음 번호

            // 다음 번호의 저장되어 있는 최소 횟수가 현재 이동 횟수보다 클 때
            if(visited[nx] > visited[x]+1){
                visited[nx] = visited[x]+1; // 갱신
                q.push(nx); // 큐에 넣음
            }
        }
    }
}

핵심이 되는 BFS 함수이다.
visited을 통해 방문 체크 및 이동 최소 횟수를 저장한다.

먼저 무조건 출발은 1번에서 시작하기 때문에
visited [1] = 0으로 초기화해 준다.

그리고 bfs를 돌릴 때 x > 100이 넘어갈 때는 패스해 주고, 
항상 주사위가 1 ~ 6일 때의 이동을 모두 해준다.

각 이동 위치에서 뱀이나 사다리가 있는지를 확인한다. 
map 배열 안에 0이 아니라면 뱀이나 사다리라는 것이다.

그렇다면 nx에 연결된 번호를 넣어준다.
그렇지 않다면, 현재 x에 주사위 번호만큼을 더해준다.

이후 그 자리에 있는 visited배열과 비교하여
더 작은 이동 횟수를 가진 것으로 해당 배열을 갱신해 준다.
그리고 더 작다면 그 큐를 안에 넣는다.

여기까지가 핵심함수에 대한 설명의 끝이고,
나머지는 메인 함수에 대해 설명하고 마치겠다.

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int N,M;
int map[101]= {0,};
int visited[101]; // 방문 체크


void bfs(int sx){
    queue<int> q;
    visited[sx] = 0; // 출발 위치
    q.push(sx); // 1 큐에 넣음

    while(!q.empty()){
        int x = q.front();
        q.pop();
        if(x > 100) continue; // 100이 넘는 값은 넘김
        for(int i = 1; i <= 6; i++){
            int nx;
            // 100 이하 && 사다리 또는 뱀일때 
            if(x+i <= 100 && map[x+i]) nx = map[x+i]; // 연결된 번호를 nx로
            else nx = x+i; // 그게 아니면 다음 번호

            // 다음 번호의 저장되어 있는 최소 횟수가 현재 이동 횟수보다 클 때
            if(visited[nx] > visited[x]+1){
                visited[nx] = visited[x]+1; // 갱신
                q.push(nx); // 큐에 넣음
            }
        }
    }
}


int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        int v1, v2;
        cin >> v1 >> v2;
        map[v1] = v2;
    }
    for(int i = 0; i < M; i++){
        int v1, v2;
        cin >> v1 >> v2;
        map[v1] = v2;
    }

    for(int i = 0; i <= 100; i++) visited[i] = 9999;
    bfs(1);

    cout << visited[100];
}

여기서 볼 것은 visited을 9999로 초기화하는 것이다.
왜냐하면 우리가 구해야 하는 것은 최솟값이기 때문이다.

최종적으로 구해야 하는 것은 100일 때의 최솟값이기 때문에
visited [100] 일 때를 출력해 준다.

 

---

시행착오

쩝.. 또 못 풀었네..
쉬운 문제라고 하던데 못 푸니까 화난다. 좀 풀고 싶다.

어째 풀면 풀수록 더 못 푸는 것 같다.
공부를 잘못하고 있는 건지 슬럼프인 건지는 모르겠는데..

이번에는 접근 자체를 잘못했다.

백트래킹으로 접근했고 이게 BFS인지는 전혀 몰랐다.
Segment Fault로 고생하다가 1시간이 훌쩍 지나가버려서 그냥 답을 봤다.

쉬운 문제라고 하니까 멘털이 확 나가더라.
다음 문제는 꼭 맞히자.

https://toss.me/howudong

howudong님에게 보내주세요