[백준] 16928번 뱀과 사다리 게임 JAVA (자바) 풀이

문제 16928(BFS)

 

 :  주사위를 조작해 원하는 수를 만들면 최소 몇 번만에 도착할까

    게임은 크기가 10×10이고, 총 100개의 칸으로 된 보드판은 1~100까지 수가 적혀있다

    주사위를 굴려 나온 수만큼 이동

 

 :  예) 현위치 =  i  /  주사위 = 4라면 i+4번 칸으로 이동

 

 :  도착칸 = 사다리 경우 위로 이동  /  도착칸 = 뱀 경우 뱀을 따라 이동

    모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있다 (동시에 둘 다 갖는 경우는 없다)

  

 :  게임의 목표 = 1번 칸에서 시작해서 100번 칸에 도착하는 것

    100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값 구하기

 

 

[입력]

 :  첫째 줄에 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)

 

 :  둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)

    x번 칸에 도착하면, y번 칸으로 이동한다는 의미

 

 :  다음 M개의 줄에는 뱀의 정보를 의미하는 u, v (u > v)

    u번 칸에 도착하면, v번 칸으로 이동한다는 의미

    1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다

  

 

 [출력]

 :  100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 출력

 

 

 

 [문제접근]

 

1. 뱀 & 사다리 이동하는 건 마찬가지 배열 한개만 사용!

• 뱀이든 사다리든 이동하는 건 마찬가지 두가지 동선이 겹치지 않기 때문에 arr 배열 안에 넣기

 

2. 출력 배열 사용하지 말고 큐에다 넣어버리기

• count[] 배열보다 큐 자체에 넣는 것이 더 간단하다 q.add(new int{start,0}) 추천

 

3. for문 상하좌우 이동을 떠올릴 것

• for문 6번 (갈 수 있는 방향 6가지)
  처음에는 무조건 주사위 돌리기 (시작지점에는 뱀과 사다리 없다)
  
  • arr에 값이 있는지 확인
    • 값이 있다면 주사위 없이 뱀 혹은 사다리를 통해 이동가능
      큐에 넣어서 주사위 카운트하는 것 없이 next 지점만 arr[next]로 변경
  • arr값 확인 끝나면 최종적으로 나온 next지점을 다시 큐에 넣어 주사위 돌리기

 

4. 왜 if - else문이 아니라 if - if문인가! (연달아 뱀이나 사다리는 없다!)

• arr 값을 확인한 뒤 갱신된 다음은 무조건 주사위를 돌려야한다
• 모든 칸에는 뱀 하나 사다리 하나가 최대이다
  (예 1번에서 5번으로 이동하는 사다리가 있다면 5번은 빈칸이어야 한다)
  
  
• 두개의 if 문을 모두 돌려야하기 때문에 if-else는 사용불가이다
  • 첫번째 if문은 뱀이나 사다리를 통해 이동한 next 지점을 찾기위함
  • 두번째 if문은 비어있는 칸이므로 주사위를 돌려서 next 지점을 찾기 위함

 

5. visit 크기

• N의 입력이 1번부터 100번까지라 검사를 위해 배열은 101로 설정
• 방문처리를 하고나서 큐에 넣어야 하기때문에 방문체크가 큐 추가보다 더 우선이다

 

6. bfs를 for문이나 재귀에 사용하지 말 것

• for(){ bfs } 하지말 것 (bfs 메서드 내에서 큐에 계속 추가하면서 반복하면 된다)
• bfs메서드 내에서 다시 bfs를 호출하지 말 것 (백트래킹이나 dfs와는 다르다)

       

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int arr[],N,M;
    static boolean visit[];
    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());
        arr = new int[101];
        visit = new boolean[101];
        
        for(int i=0; i<N+M; i++){
            st = new StringTokenizer(br.readLine());
            int x =Integer.parseInt(st.nextToken());
            int y =Integer.parseInt(st.nextToken());
            arr[x]=y;
        }
        
        bfs(1);
    }
    static void bfs(int start){
        Queue<int[]>q=new LinkedList<>();
        q.add(new int[]{start,0});
        visit[start]=true;
        
        while(!q.isEmpty()){
            int p[] = q.poll();
            
            if(p[0]==100){
                System.out.println(p[1]);
                return;
            }
            
            for(int i=1; i<7; i++){
                int next = p[0]+i;
                if(next<=100){
                    if(arr[next]!=0){
                        next = arr[next];
                    }
                    if(!visit[next]){
                        visit[next] = true;
                        q.add(new int[]{next,p[1]+1});
                        
                    }
                }
            }
        }
    }
}

 

 [해설]
     

 :  static int arr[],N,M;
    static boolean visit[];

 

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());

    M = Integer.parseInt(st.nextToken());
    arr = new int[101];  뱀이든 사다리든 이동 정보 저장
    visit = new boolean[101];  방문배열
        

 :  for(int i=0; i<N+M; i++){
            st = new StringTokenizer(br.readLine());
            int x =Integer.parseInt(st.nextToken());  x 칸에서
            int y =Integer.parseInt(st.nextToken());  y 칸으로 이동가능
            arr[x]=y;  x-y가 이동수단으로 이어졌으니 중복을 피해 y는 빈칸
    }

 :  bfs(1);  bfs 1지점부터 실행
    
    
 :  static void bfs(int start){  
        Queue<int[]> q = new LinkedList<>();  큐 선언
        q.add(new int[] {start,0});  큐 추가
        visit[start]=true;  방문처리
        
        while(!q.isEmpty()){
            int p[] = q.poll();  큐에서 뽑기
            if(p[0]==100){ 100이면 종료조건
                System.out.println(p[1]);  주사위 카운트 출력
                return;
            }

            for(int i=1; i<7; i++){  주사위 6가지 방향으로 이동가능
                int next = p[0]+i;  6가지 방향 더해보기

                if(next<=100){  해당 지점은 100을 넘어서는 안된다
                    if(arr[next]!=0){  다음지점에 이동수단(arr)이 있다면
                        next = arr[next];  큐에 넣어서 주사위 돌리지 말고 바로 그 지점으로 이동
                    }

                    if(!visit[next]){  갱신된 지점 혹은 애초에 해당칸이 수단없는 빈칸이라면
                        visit[next] = true;  방문 처리 후
                        q.add(new int[]{next,p[1]+1});  큐에 추가해서 주사위 돌리기
                    }
                }
            }
   }



 

 

이제 풀어보러 갈께요 :)

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

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