[16928] 뱀과 사다리 게임
문제 분석
2차원 배열이 주어진다.
1번 ~ 100번 까지 있다. (10x10)
주사위를 굴려 선택적으로 이동할 수 있다. 최소 1칸 ~ 최대 6칸
뱀과 사다리가 주어진다.
뱀은 윗칸에서 아랫칸으로 내려간다. (ex 23 -> 11 , 23번 에 도착하면 11번 으로 내려간다.)
사다리는 아랫칸에서 윗칸으로 올라간다. (ex 8 -> 67 , 8번 에 도착하면 67번 으로 내려간다.)
1번 부터 시작을 해서 100번 까지 도착할 수 있는 경우의 수 중 최솟값 을 리턴해라.
뱀과 사다리를 잘 이용해야 한다.
항상 100번 칸에 도착할 수 있는 경우의 수만 주어진다.
풀이 과정
🎯 뱀과 사다리는 중요하지 않다. 단지 이동할 뿐.
올라가거나 내려가는 건 신경쓰지 않아도 된다.
단지 x번 칸에서 y번 칸으로 이동한다 가 중요하다.
사이즈는 정해져 있다. (10x10)
배열을 하나 선언하고 이동할 수 있는 위치들을 담아보자.
int[] map = new int[101];예제 1을 기준으로 보자면 아래처럼 x --> y 로 이동한다고 볼 수 있다.
32 --> 62
42 --> 68
12 --> 98
95 --> 13
97 --> 25
93 --> 37
79 --> 27
75 --> 19
49 --> 47
67 --> 17입력받아서 잘 자른다음에 아래와 같이 담자.
for (int i = 0; i < ladders + snakes; i++) {
st = new StringTokenizer(br.readLine());
int startIndex = Integer.parseInt(st.nextToken());
int endIndex = Integer.parseInt(st.nextToken());
map[startIndex] = endIndex;
}🎯 효율적인 탐색을 위해 재방문 금지
최대 10x10 사이즈이기 때문에 아래와 같이 선언한다.
boolean[] visited = new boolean[101];🎯 시작 위치는 1번이다.
Queue<Integer> queue = new LinkedList<>();
queue.add(1);필자는 선입선출 구조의 Queue 를 사용했다.
🎯 Queue 사용 이유는 주사위의 숫자를 선택적으로 뽑기 때문.
1번 칸에서 시작한다면 다음으로 갈 수 있는 경우의 수는 2, 3, 4, 5, 6, 7 이다. (주사위는 1~6)
Queue 를 도식화해서 초반 경우의 수를 보자. (선입선출 구조다.)
🎯 주사위를 1번 굴려서 갈 수 있는 경우의 수
<-----------<---------------<-----------<
2번, 3번, 4번, 5번, 6번, 7번
<-----------<---------------<-----------<🎯 주사위를 2번 굴려서 갈 수 있는 경우의 수는
2번 에서 +1 ~ +6 이다. (3, 4, 5, 6, 7, 8)
3번 에서 +1 ~ +6 이다. (4, 5, 6, 7, 8, 9)
.....
7번 에서 +1 ~ +6 이다. (8, 9, 10, 11, 12, 13)
<-----------<---------------<-----------<
8번, 9번, 10번, 11번, 12번, 13번
<-----------<---------------<-----------<자, 여기서 2가지 핵심 로직이 있다.
재방문하지 않는 것 과 사다리 혹은 뱀으로 이동하는 위치를 같이 담아주는 것
🎯 방문하였다면 Queue 에 담지 않는다, 이동하는 위치도 같이 담아준다.
if (newNumber <= 100 && !visited[newNumber]) {
visited[newNumber] = true;
if (map[newNumber] != 0) {
visited[map[newNumber]] = true;
queue.add(map[newNumber]);
} else {
queue.add(newNumber);
}
}맨 위의 if 문의 조건은 100번 칸을 넘지 않으면서 방문하지 않아야 실행된다.
그 다음 조건문 을 통해 이동할 수 있는 값이라면 Queue 에 담아준다.
이때 방문 처리를 위해 true 로 설정해준다.
나의 생각
leetcode 에서 똑같은 문제를 풀어서 접근법이 쉬웠다.
이 문제의 요점은 사리던 뱀이던 '이동한다' 가 중요한 키포인트라고 생각한다.
개발자는 어쩌면 도메인을 관통해 솔루션을 제공해야하는 것이 아닐까 싶다.
코드
package baekjooncompletion;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class BaekJoon16928 {
private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
int[] map = new int[101];
boolean[] visited = new boolean[101];
StringTokenizer st = new StringTokenizer(br.readLine());
int ladders = Integer.parseInt(st.nextToken());
int snakes = Integer.parseInt(st.nextToken());
for (int i = 0; i < ladders + snakes; i++) {
st = new StringTokenizer(br.readLine());
int startIndex = Integer.parseInt(st.nextToken());
int endIndex = Integer.parseInt(st.nextToken());
map[startIndex] = endIndex;
}
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
int count = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int number = queue.poll();
map[number] = count;
if (number == 100) {
System.out.println(count);
return;
}
for (int j = 1; j <= 6; j++) {
int newNumber = number + j;
if (newNumber <= 100 && !visited[newNumber]) {
visited[newNumber] = true;
if (map[newNumber] != 0) {
visited[map[newNumber]] = true;
queue.add(map[newNumber]);
} else {
queue.add(newNumber);
}
}
}
}
count++;
}
System.out.println(0);
}
}
