[백준 16928, Java] 뱀과 사다리게임

문제

www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

 

실수 했던 것 

- 방문 체크 안함 (→메모리초과)

- "모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다"는 조건 : 사다리칸 - 이동 - 뱀칸 이런식으로 계속 이동할 수 있다고 생각. 현재칸에 뱀 또는 사다리가 있어서 한번 이동을 하면 끝 

 

 

 

기억해야 할 것

- queue에는 더이상 움직일 수 없는 최종 위치만 있어야 한다. 

 

코드 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	public static int[] map = new int[101];
	public static int[] rollingCount = new int[101];
	public static boolean[] visited = new boolean[101];
	public static int minRollingCount = 0;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		int N;
		int M;
		
		st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		
		for(int p = 0; p<N+M;p++) {
			st = new StringTokenizer(br.readLine(), " ");
			int point = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			
			map[point] = value;
			
		}
		findMinRolling();
		
		bw.write(String.valueOf(minRollingCount));
		bw.flush();
		

	}
	public static void findMinRolling() {
		Queue<Integer> queue = new LinkedList<Integer>();
		visited[1] = true;
		queue.add(1);
		
		while(!queue.isEmpty()) {
			int currentPoint = queue.remove();
			int currentCount = rollingCount[currentPoint];
			
			
			//현재위치가 100이면 게임종료 
			if(currentPoint == 100) {
				minRollingCount = currentCount;
				break;
			}
			
			
			//주사위를 굴린다 
			int candidatePoint =0;
			for(int dice =1; dice<=6; dice++) {
				candidatePoint = currentPoint + dice;
				
				//주사위를 굴려 이동한 위치가 100을 넘으면 이동불가 
				if(candidatePoint>100) {
					continue;
				}
				
				//이미 방문한 곳
				if(visited[candidatePoint]) {
					continue;
				}
				
				visited[candidatePoint] = true;
				//주사위를 굴려 이동한 위치에 뱀 또는 사다리가 있는지 확인 
				
				//주사위를 굴려 이동한 위치에 뱀또는 사다리가 없
				if(map[candidatePoint]==0) {
					rollingCount[candidatePoint] = currentCount +1;
					queue.add(candidatePoint);
				}
				
				//주사위를 굴려 이동한 위치에 뱀 또는 사다리가 있다 
				else {
					candidatePoint = map[candidatePoint];
					if(!visited[candidatePoint]) {
						visited[candidatePoint] = true;
						rollingCount[candidatePoint] = currentCount +1;
						queue.add(candidatePoint);
					}
					
				}
				
			}
		}
	}
}