16928번 - 뱀과 사다리 게임

1️⃣ Dijkstra Algorithm

 

✏️ 풀이 과정

1로부터 100까지의 최단경로를 찾는 문제이기 때문에 다익스트라 알고리즘을 통해 해결할 수 있습니다. 다익스트라 알고리즘을 사용하면 한 출발점으로부터 다른 모든 정점으로의 최단 거리를 구할 수 있기 때문입니다. 알고리즘을 돌리고 배열에서 100에 대한 최단거리를 읽으면 답을 구할 수 있습니다.

 

그래프로 바꿔보면 100개의 정점이 존재하는 것이기 때문에 이차원 배열을 사용하면 주사위로 갈 수 없는 정점이 대부분이라 연결되지 않은 정점이 많은 희소 행렬이 되어 낭비가 많아집니다. 이를 해결하기 위하여 인접 리스트를 사용하면 O(N^2) 대신 O(NlogN)의 시간복잡도로 문제를 해결할 수 있습니다. 이 때 문제의 조건을 반영하기 위해서 세 가지의 작업이 필요합니다.

 

첫 번째로는 1에서 각 정점까지의 거리를 저장하는 일차원 배열을 선언하고 1에서의 다른 모든 정점에 대한 거리를 무한대(Integer.MAX_VALUE로 하면 더할 때 오버플로우가 나기 때문에 Integer.MAX_VALUE-100과 같은 적당히 큰 값으로 해야 합니다.)로 설정해야 합니다.

 

두 번째는 주사위로 갈 수 있는 곳을 반영하기 위해서 모든 정점에 대해 1부터 6까지 더한 정점을 인접 리스트에 추가하여 연결 상태로 만들어주는 것입니다. 여기서는 Node 클래스를 설정하여 정점 번호와 가중치(거리)를 저장했습니다. 주사위로 갈 수 있는 경우 거리는 1이 됩니다. 주의할 점은 95부터는 for문을 따로 설정해주거나 처음 배열을 선언할 때 106개를 선언해야 에러가 발생하지 않습니다.

 

마지막 세 번째는 뱀과 사다리를 반영하는 것입니다. 여기서 주의할 점은 뱀 혹은 사다리가 있는 칸에 갈 경우 반드시 타고 이동해야 한다는 것입니다. 즉 뱀이나 사다리가 있는 칸에 머무를 방법이 없습니다.(그 칸에서 주사위를 던지는 게 불가능합니다.) 이를 구현하기 위해서 뱀, 사다리가 있는 칸을 주사위로 갈 수 있는 모든 칸에 대해 인접 리스트에서 이동 장소로 향하는 가중치 1짜리 노드를 추가해야 합니다. 또한 뱀이나 사다리가 있는 정점들은 Integer.MIN_VALUE로 설정하여 다익스트라 알고리즘 적용 중 생성된 최적이 아닌 중간 값 제거를 위한 매커니즘에(거리가 현재까지 구한 최적 거리보다 큰 경우) 걸러지게 만듭니다.

 

위 작업들을 마치고 PriorityQueue를 사용해서 다익스트라 알고리즘을 돌리면 dist[100]에서 답을 얻어낼 수 있습니다.

 

💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	static class Node implements Comparable<Node> {
		int v;
		int dist;
		Node link;
		
		public Node(int v, int dist, Node link) {
			this.v = v;
			this.dist = dist;
			this.link = link;
		}
		
		@Override
		public int compareTo(Node o) {
			return this.dist - o.dist;
		}
	}
	
	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());
		Node[] adjList = new Node[101];
		int[] dist = new int[101];
		for(int i=2;i<=100;i++) {
			dist[i] = Integer.MAX_VALUE - 100;
		}
		for(int i=1;i<=94;i++) {
			for(int j=1;j<=6;j++) {
				adjList[i] = new Node(i+j, 1, adjList[i]);
			}
		}
		for(int i=95;i<=99;i++) {
			for(int j=1;j<=6-i+94;j++) {
				adjList[i] = new Node(i+j, 1, adjList[i]);
			}
		}
		int from, to;
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			from = Integer.parseInt(st.nextToken());
			to = Integer.parseInt(st.nextToken());
			dist[from] = Integer.MIN_VALUE;
			for(int j=from-6;j<=from-1;j++) {
				if(j >= 0) {
					adjList[j] = new Node(to, 1, adjList[j]);
				}
			}
		}
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			from = Integer.parseInt(st.nextToken());
			to = Integer.parseInt(st.nextToken());
			dist[from] = Integer.MIN_VALUE;
			for(int j=from-6;j<=from-1;j++) {
				if(j >= 0) {
					adjList[j] = new Node(to, 1, adjList[j]);
				}
			}
		}
		PriorityQueue<Node> pq = new PriorityQueue<>();
		Node cur;
		pq.offer(new Node(1, 0, null));
		while(!pq.isEmpty()) {
			cur = pq.poll();
			if(dist[cur.v] < cur.dist) {
				continue;
			}
			for(Node n=adjList[cur.v];n!=null;n=n.link) {
				if(dist[n.v] > dist[cur.v] + n.dist) {
					dist[n.v] = dist[cur.v] + n.dist;
					pq.offer(new Node(n.v, dist[cur.v] + n.dist, null));
				}
			}
		}
		System.out.println(dist[100]);
		br.close();
	}
}

 

2️⃣ BFS

 

문제 분류를 보니 원래는 BFS로 해결하는 문제인 듯 합니다. 향후 시간이 나면 업데이트하겠습니다. 단계 수를 체크하는 BFS로 뱀과 사다리에서 순간이동 처리를 해주고 100에 도달하는 순간 종료하여 문제를 해결할 수 있을 것으로 보여집니다.