알고리즘 풀이 - 백준 16928(뱀과 사다리 게임, 그래프(BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

주사위를 굴려 1에서 100번째 위치로 최소한의 이동으로 이동하는 횟수를 구하는 문제(사다리, 뱀에 의해 위치는 조정될 수 있음)

 

 

2. 풀이

 

BFS를 통해 최소 이동 횟수를 구하는 문제이다.

초반에는 (0, 1)을 탐색 완료로 표시하고 주사위를 굴려서 1~6까지 Position 값을 더해서 구한 뒤 해당 위치에 맞는 index 값을 계산하여 탐색을 수행하면 된다.

 

게임판 크기가 10x10이므로 간단하게 index를 구할 수 있다.

예를 들어 72번 위치라면 행(y) 번호의 index는 72를 10으로 나눈 몫이 되어 7이 된다.
열(x) 번호의 index는 72를 10으로 나눈 나머지로 구하여 2가 된다.

즉, 72번 위치는 (7, 2)가 된다. 가장 큰 100번은 (10, 0)이 되므로 게임판의 크기를 10x10으로 만들고 Queue에 해당 위치를 넣을 수는 없으니, 100의 값이 나오면 Queue에 넣지 않고 바로 게임을 끝내야 한다.(혹은 11x10으로 생성)

 

코드를 통해 문제 해결 방법을 알아보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

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

public class Main{
    static int n;
    static int m;
    
    // board는 현재 움직인 횟수, move는 사다리, 뱀의 위치를 저장한다.
    static int[][] board = new int[10][10];
    static int[][] move = new int[10][10];
    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());
        
        // 주어진 값들을 저장한다.
        // 사다리, 뱀에 의해 이동이 필요한 위치는 별도의 배열 move에 저장
        for(int i=0; i < n+m; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            
            int uy = u / 10; int ux = u % 10;
            
            move[uy][ux] = v;
        }
        
        // BFS 탐색 수행
        bfs();
        br.close();
    }
    
    private static void bfs(){
         Queue<Pos> q = new LinkedList<>();
         
         // (0, 1) == 1번 위치이므로 이것을 저장
         q.offer(new Pos(0, 1, 0));
         
         while(!q.isEmpty()){
             Pos c = q.poll();
             
             // 행 값에 10 곱하고 열 값을 더하면 전체 Position 숫자가 나온다.(1~100)
             int p = 10 * c.y + c.x;
             
             // 주사위를 굴려서 나올 수 있는 숫자를 다 추가한다.
             for(int i=1; i <= 6; i++){
                 int np = p + i;
                 
                 // Position 값을 다시 행 열 값으로 바꾼다.
                 int ny = np / 10; 
                 int nx = np % 10;
                 
                 // 현재 100이 나왔다면 추가 탐색은 불 필요하다.
                 if(np == 100) {
                     System.out.println(c.move+1);
                     return;
                 }
                 
                 // 범위를 벗어난 경우에는 다시 수행
                 if(np > 100 || board[ny][nx] != 0) continue;
                 
                 // 이동 횟수 저장
                 board[ny][nx] = c.move+1;
                 
                 // 만약 뱀 / 사다리의 값이 저장된 위치라면 그 위치를 Queue에 넣는다.
                 if(move[ny][nx] != 0){
                     int my = move[ny][nx] / 10;
                     int mx = move[ny][nx] % 10;
                     if(board[my][mx] == 0) {
                         board[my][mx] = c.move+1;
                         q.offer(new Pos(my, mx, c.move+1));
                     }
                 // 뱀, 사다리가 없으면 현재 위치를 저장
                 } else {
                     q.offer(new Pos(ny, nx, c.move+1));
                 }
             }
         }
    }
}

class Pos{
    int y;
    int x;
    int move;
    public Pos(int y, int x, int move){
        this.y = y;
        this.x = x;
        this.move = move;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.