[백준] 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지점을 다시 큐에 넣어 주사위 돌리기
- arr에 값이 있는지 확인
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}); 큐에 추가해서 주사위 돌리기
}
}
}
}
이제 풀어보러 갈께요 :)
* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *