백준 16928 (뱀과 사다리 게임) - java

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

16928번: 뱀과 사다리 게임

뱀과 사다리 경우에 대한 정보를 HashMap에 저장하고 푸는 문제이다. 중복되는 경우 한 지점에 뱀과 사다리가 모두 존재하는 경우가 없기 때문에 Map 자료 구조를 사용할 수 있는 문제이다.

 

주사위를 굴려 해당 지점에 대한 방문 처리를 하고 뱀과 사다리가 있는 경우와 없는 경우를 나눠서 처리하고 큐에 저장하여 탐색을 진행하면 쉽게 문제를 풀 수 있다.

 

import java.io.*;
import java.util.*;
public class Main {
    static int[] visit = new int[101];
    static int n= 0;
    static int m= 0;
    static HashMap<Integer,Integer> map = new HashMap<>(); // 뱀과 사다리 정보
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for(int i=1;i<=n+m;i++)
        {
            st = new StringTokenizer(br.readLine()," ");
            int start = Integer.parseInt(st.nextToken());
            int goal = Integer.parseInt(st.nextToken());

            map.put(start,goal); // 뱀과 사다리 정보를 저장
        }
        int result = bfs();
        System.out.println(result);
        br.close();
    }

    static int bfs()
    {
        Queue<Integer> q = new LinkedList<>();
        q.add(1); // 시작 지점 1 (고정)
        visit[1]=1; // 시작 지점 방문 처리
        int result = 0;
        while(!q.isEmpty())
        {
            int cur = q.poll();

            if(cur==100) // 도착지점인 경우 (최솟값을 구해야 한다)
            {
                if(result==0) // 처음 도달한 경우
                    result = visit[cur];
                else if(visit[cur]<result) // 더 작은 값을 찾은 경우
                    result = visit[cur];
            }
            for(int i=1;i<=6;i++)
            {
                int nx = cur + i;
                if(nx>=101) // 해당 범위인지 확인 , 주사위 숫자는 양수 값이 범위를 넘어가는 경우만 존재
                    continue;
                
                // 처음 방문하거나 더 작은 횟수로 방문한 경우
                if(visit[nx]==0||visit[nx]>visit[cur]+1) 
                {
                    visit[nx]= visit[cur]+1; // 방문 처리
                    if(map.containsKey(nx)) // 뱀과 사다리가 있는 경우
                    {
                        int val = map.get(nx);
                        if(visit[val]==0||visit[val]>visit[cur]+1)
                        {
                            visit[val] = visit[cur]+1; // 뱀과 사다리로 이동한 지점의 방문 처리
                            q.add(val); // 마지막 위치를 큐에 추가
                        }
                    }
                    else{
                        q.add(nx); // 뱀과 사다리가 없는 경우 단순 이동 위치를 큐에 추가
                    }
                }
            }
        }
        return result -1; // 최솟값 반환 (시작 지점의 방문 값이 1이기 때문에 1 차감)
    }
}