[백준] 16928-뱀과 사다리 게임(JAVA) (BFS , Map)

※ 아이디어

• 현재 위치에서 주사위를 굴려 이동할 수 있는 번호를 큐에 담는다
• 이 때 그 칸이 사다리/뱀인 경우 → 사다리/뱀을 타고 도착하게될 칸의 번호로 담는다
• 사다리/뱀을 타고 이동하는 경우 주사위를 굴려 이동하는게 아니기 때문에 카운팅은 하지 않는다
• 사다리, 뱀의 정보는 꺼내 쓰기 좋게 Map을 사용하는게 좋겠다고 생각했다 ( O(1) 이니까)
• 문제에서 항상 100번 칸에 도착할 수 있는 입력만 주어진다 라고 했으니 큐에서 꺼낸놈의 번호가 100이면 바로 종료
  (큐의 특성상 주사위를 굴린 횟수가 1, 1, ..., 1, 2, 2, ..., 2, 3, 3, ... 이런식으로 될거기때문에)

※ 놓쳤던 점

• 처음에는 사다리/뱀을 타고 도착하게 될 칸도 방문 체크를 했었는데, 그렇게 하게 되면 다른 경우를 체크하지 못할 수 있다
  • 예) 사다리를 타고 50번에 도착해 방문체크를 했다 가정 → 주사위를 굴려 50번에 도착하거나, 뱀을 타고 50번에 도착하는 경우를 거르게 됨
• 사다리/뱀을 타고 도착한 곳에 또 사다리/뱀이 있는 경우를 생각하지 못했다

 

 

[맞은 코드]

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

public class Main {
	static int n;
	static int m;
	static boolean[] visited;
	static Map<Integer, Integer> ladderMap = new HashMap<>();
	static Map<Integer, Integer> snakeMap = 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());	
		visited = new boolean[101];
		
		// 1. 사다리 정보 입력
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			int ladderIndex = Integer.parseInt(st.nextToken());
			int ladderDestination = Integer.parseInt(st.nextToken());
			ladderMap.put(ladderIndex, ladderDestination);
		}
		// 2. 뱀 정보 입력
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int snakeIndex = Integer.parseInt(st.nextToken());
			int snakeDestination = Integer.parseInt(st.nextToken());
			snakeMap.put(snakeIndex, snakeDestination);
		}
		
		int rv = bfs();
		
		System.out.println(rv);
	}
	
	private static int bfs() {
		// 3.bfs로 탐색
		Queue<int[]> que = new LinkedList<>(); // {위치, 주사위굴린 횟수}
		que.add(new int[] {1, 0}); // 시작위치=1, 굴린횟수=0
		visited[1] = true;
		
		while(!que.isEmpty()) {
			int[] curNode = que.poll();
			int curIndex = curNode[0];
			int curTry = curNode[1];
			
			if(curIndex == 100) {
				return curTry;
			}
			
			for(int i=1; i<=6; i++) {
	            int nextIndex = curIndex + i;
	            if(nextIndex > 100) continue;
	            
	            int dest = getDestination(nextIndex); // 사다리/뱀 최종 목적지 계산 (사다리 타고 도착한 곳에 또 사다리/뱀이 있는 경우 등)
	            
	            if(!visited[dest]) {
	                visited[dest] = true;
	                que.add(new int[] {dest, curTry + 1});
	            }
	        }
		}
		
		return 0;
	}
	
	// 사다리/뱀이 있으면 최종 목적지까지 한번에 이동
	private static int getDestination(int pos) {
	    while(ladderMap.containsKey(pos) || snakeMap.containsKey(pos)) {
	        if(ladderMap.containsKey(pos)) pos = ladderMap.get(pos);
	        else pos = snakeMap.get(pos);
	    }
	    return pos;
	}
}

 

 

[틀린 코드] 

- 사다리/뱀을 타고 이동할 때 방문체크를 했었다

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken()); 
		int m = Integer.parseInt(st.nextToken());	
		boolean[] visited = new boolean[101];
		
		// 1. 사다리 정보 입력
		Map<Integer, Integer> ladderMap = new HashMap<>();
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			int ladderIndex = Integer.parseInt(st.nextToken());
			int ladderDestination = Integer.parseInt(st.nextToken());
			ladderMap.put(ladderIndex, ladderDestination);
		}
		// 2. 뱀 정보 입력
		Map<Integer, Integer> snakeMap = new HashMap<>();
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int snakeIndex = Integer.parseInt(st.nextToken());
			int snakeDestination = Integer.parseInt(st.nextToken());
			snakeMap.put(snakeIndex, snakeDestination);
		}
		
		// 3.bfs로 탐색
		Queue<int[]> que = new LinkedList<>(); // {위치, 주사위굴린 횟수}
		que.add(new int[] {1, 0}); // 시작위치=1, 굴린횟수=0
		int minTry = 17;
		
		while(!que.isEmpty()) {
			int[] curNode = que.poll();
			int curIndex = curNode[0];
			int curTry = curNode[1];
			
			visited[curIndex] = true;
			
			if(curIndex == 100) {
				minTry = Math.min(minTry, curTry);
			}
			
			// 현재 위치가 사다리 또는 뱀이면 주사위를 굴리지 않고 바로 이동
			if(ladderMap.containsKey(curIndex)) {
				que.add(new int[] {ladderMap.get(curIndex), curTry}); // 주사위는 안굴리기 때문에 1 증가 해주지 않음
				continue;
			}
			if(snakeMap.containsKey(curIndex)) {
				que.add(new int[] {snakeMap.get(curIndex), curTry}); // 주사위는 안굴리기 때문에 1 증가 해주지 않음
				continue;
			}
			
			for(int i=1; i<=6; i++) { // 주사위를 굴려서 나올수 있는 경우 6가지
				int nextIndex = curIndex + i;
				if(nextIndex<= 100 && !visited[nextIndex])
					que.add(new int[] {nextIndex, curTry + 1});
			}
		}
		
		System.out.println(minTry);
	}
}