[백준] 단계별로 풀어보기(단계:25, 그래프와 순회,JAVA)16928번, 뱀과 사다리 게임

문제 링크

16928번: 뱀과 사다리 게임

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

BFS

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

뱀과 사다리 게임에 대한 정보

뱀과 사다리 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 게임은 1번 칸에서 시작해서 100번칸에 도착해야 한다.

2. 마지막에 100번 칸에 딱 맞게 도착해야합니다.

3. 사다리가 있는 지점에 도착하면 사다리가 가리키는 지점으로 이동합니다.

4. 뱀이 있는 지점에 도착하면 뱀이 가리키는 지점으로 이동합니다.

 

1번 칸에서부터 BFS탐색을 시작하여 가장 먼저 100번 칸에 도착하는 횟수를 구하였습니다.

 

BFS를 진행 과정

1.

 

1번칸을 시작으로 주사위 1~6번이 나올 때

이동할 지점이 방문하였다면 이동 X

이동할 지점이 방문하지 않았다면 이동합니다.

 

2.

이동한 지점이 사다리나 뱀인 경우 그에 대응하는 지점으로 이동하기

 

3.

위 과정을 반복하여 100번칸에 도착하였을 때 지금까지 주사위를 던진 횟수를 반환합니다.

가장 먼저 100번 칸에 도착한 주사위 던진 횟수가 최소로 던진 주사위 횟수입니다.

 

가장 먼저 100번 칸에 도착했을 때 주사위 던진 횟수를 결과로 출력하였습니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 N,M과 사다리와 뱀의 정보를 저장하였습니다.
• BFS로 1칸부터 100칸에 도착하는 게임을 탐색하는 game함수를 만들었습니다.
• BufferedWriter에 BFS탐색으로 가장 먼저 100칸에 도착하는 주사위 횟수를 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• game은 visited[], ladder[], snake[]와 Queue를 이용하여 방문 여부 확인과 주사위 1~6번에 따른 칸을 이동합니다.
• game은 100칸에 먼저 도착한 주사위 횟수가 최소 던진 주사위 횟수이므로 먼저 도착했을 때 횟수를 결과로 반환하빈다.

결과 코드

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

public class Main {
	//보드에 대한 정보
	static class boardPoint{
		int cur, count;
		public int getCur() {
			return cur;
		}

		public int getCount() {
			return count;
		}

		public boardPoint(int cur, int count) {
			this.cur = cur;
			this.count = count;
		}

	}
	static int N,M;
	static int[] ladder = new int[101];	//사다리 정보
	static int[] snake = new int[101];	//뱀 정보
	static boolean[] visited = new boolean[101];	//보드 칸 저장 정보
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
        //사다리 정보 저장
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		int x = Integer.parseInt(st.nextToken());
    		int y = Integer.parseInt(st.nextToken());
    		ladder[x] = y;
    	}
        //뱀 정보 저장
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		int u = Integer.parseInt(st.nextToken());
    		int v = Integer.parseInt(st.nextToken());
    		snake[u] = v;
    	}
    	int result = game();	//BFS를 통한 게임 진행 및 최소 주사위 던진 횟수 저장
    	bw.write(result + "\n");	//최소 주사위 던진 횟수 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //BFS을 탐색을 통한 게임을 진행하여 가장 먼저 100칸에 도착하는 주사위 횟수를 구하는 함수
    static int game() {
    	Queue<boardPoint> queue = new LinkedList<boardPoint>();
    	queue.add(new boardPoint(1, 0));
    	visited[1] = true;	//시작칸 방문 확인
    	while(!queue.isEmpty()) {
    		boardPoint temp = queue.poll();
    		int cur = temp.getCur();
    		int count = temp.getCount();
    		if(cur==100)		//100칸 도착했을 때
    			return count;		//주사위 던진 횟수 반환
    		for(int i=1;i<=6;i++) {		//주사위 1~6번일 때
    			int next = cur + i;
    			if(next<=100 && !visited[next]) {	//이동할 때 방문하지 않았을 경우
    				visited[next] = true;
    				if(ladder[next]!=0) {		//이동한 칸이 사다리인 경우
    					visited[ladder[next]] = true;
    					queue.add(new boardPoint(ladder[next], count+1));
    				}else if(snake[next]!=0) {	//이동한 칸이 뱀인 경우
    					visited[snake[next]] = true;
    					queue.add(new boardPoint(snake[next], count+1));
    				}else {		//이동한 칸이 일반적인 칸인 경우
    					queue.add(new boardPoint(next, count+1));
    				}
    			}
    		}
    	}
    	return 0;
    }
}