[BAEKJOON] 16928 뱀과 사다리 게임 (C++, Java)

[ 문제 ]

1~100까지의 게임판에 뱀이나 사다리가 무작위로 놓여져있을 때,

가장최소치로 100까지가는 방법을 구하시오

[ 조건 ]

(1) 주사위는 1~6까지의 수

(2) 뱀이나 사다리가있으면 타고 이동할것, 단 시작부분과 끝부분에는 존재하지않음

(3) 범위는 1~100

[ 순서도 ]

(1) 입력받은 뱀 또는 사다리의 정보를 저장하는 개체생성

(2) 게임판에 최소로 도달한 값을 저장하는 개체생성

(3) 주사위의 최대수는 6이고 게임판시작부분이 1인것을 유념하고 최소값을 저장하며 bfs시작

(4) 도달한 곳에 뱀 또는 사다리가 존재한다면, 도착한 지점과 이동후 지점의 값 갱신하며 bfs

(5) 100에 도달하였어도 최소치가 아닐 수 있으므로 queue는 끝내지않고 최소값만 저장

 

[ 핵심소스코드 / C++ ]

[ 전체소스코드 / C++ ]

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#pragma warning(disable:4996)
using namespace std;

#define endl "\n"
#define tap "\t"
#define MAX 101
#define INF 2147483647

int bridge, snake;
vector <int> b[MAX];
vector <int> s[MAX];

typedef struct data {
    int idx;
    int cnt;
}Data;

int visit[MAX];
int least = INF;

void solve() {
    memset(visit, -1, sizeof visit);
    queue <Data> q;
    q.push({ 1, 0 });
    visit[1] = 0;

    while (!q.empty()) {
        Data out = q.front(); q.pop();
        if (out.idx == 100) {
            least = least < out.cnt ? least : out.cnt;
            continue;
        }
        for (int i = 1; i <= 6; i++) {
            int next = out.idx + i;
            int nc = out.cnt + 1;
            if (next <= 100)
                if (visit[next] == -1 || visit[next] > nc) {
                    visit[next] = nc;
                    if (b[next].size())
                        next = b[next][0];
                    else if (s[next].size())
                        next = s[next][0];
                    q.push({ next, nc });
                }
        }
    }
    cout << least;
}

int main() {
#ifdef _CONSOLE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int temp1, temp2;
    cin >> bridge >> snake;
    for (int i = 0; i < bridge; i++) {
        cin >> temp1 >> temp2;
        b[temp1].push_back(temp2);
	}
    for (int i = 0; i < snake; i++) {
        cin >> temp1 >> temp2;
        s[temp1].push_back(temp2);
    }
    solve();
}

 

 

[ 핵심소스코드 / Java ] 
[ 전체소스코드 / Java ]

import java.io.*;
import java.util.*;

class Pair {
    int index;
    int count;

    public Pair(int index, int count) {
        this.index = index;
        this.count = count;
    }
}

public class Main {
    final static int MAX = 101;
    final static int INF = 2147483647;

    static int answer = INF;
    static HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
    static boolean visit[] = new boolean[MAX];

    public static void solve() {
        Queue<Pair> q = new LinkedList<>();
        Pair start = new Pair(1, 0);
        q.add(start);
        visit[1] = true;

        while (!q.isEmpty()) {
            Pair out = q.poll();
            if (out.index == 100) {
                answer = answer < out.count ? answer : out.count;
                continue;
            }
            for (int i = 1; i <= 6; i++) {
                Integer next = out.index + i;
                Integer nc = out.count + 1;

                if (next <= 100 && !visit[next]) {
                    visit[next] = true;
                    if (m.containsKey(next))
                        next = m.get(next);
                    q.add(new Pair(next, nc));
                }
            }
        }

        System.out.println(answer);
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt(), b = sc.nextInt();
		
        for (int i = 0; i < s+b; i++) {
            int temp1 = sc.nextInt();
            int temp2 = sc.nextInt();
            m.put(temp1, temp2);
        }
        Arrays.fill(visit, false);
        solve();

        sc.close();
	}
}