[백준] 16928 뱀과 사다리 게임 - BFS JAVA

https://www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

코드설명

BFS 문제입니다.

 

문제에 주어진 대로 구현하면됩니다.

문제를 풀면서 조금 신경쓰였던점은, visited를 처리했을떄 과연 모든 경우를 탐색하는것이 맞을까 라는 생각이 들었습니다.

우선 visited를 사용하여 중복되는 연산을 줄여야하며,

중요한점은 사다리의 시작위치에 visited를 처리하는것이 아닌, 사다리를 통해 이동한곳을 visited 처리합니다. 

즉, 사다리를 타고 이동한곳에 visited를 처리. 혹은 뱀을 타고 도착한 곳에 visited 처리를 하여 최소의 연산 횟수를 보장합니다.

 

코드

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 Main {
	
	public static int N, M;
	public static int[] dir = {1,2,3,4,5,6};
	public static int[] ladder = new int[101];
	public static int[] snake = new int[101];
	public static boolean[] visited = new boolean[101];
	public static int answer = 0;
    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());
    	
    	for(int i=0;i<N;i++) { //사다리 정보
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		ladder[a] = b;
    	}
    	for(int i=0;i<M;i++) { //뱀 정보
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		snake[a] = b;
    	}
    	
    	simulate(new Node(1, 0));
    	
//    	System.out.println(answer);
    }
    
    public static void simulate(Node start) {
    	Queue<Node> q = new LinkedList<Node>();
    	q.offer(start);
    	visited[1] = true;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int pos = temp.pos;
    		int cnt = temp.cnt;
    		for(int dice=0;dice<6;dice++) {
    			int nPos = pos + dir[dice];
    			if(ladder[nPos] > 0) {
    				nPos = ladder[nPos];
    			}
    			else if(snake[nPos] > 0) {
    				nPos = snake[nPos];
    			}
    			if(nPos == 100) {
    				System.out.println(cnt+1);
    				return ;
    			}
    			if(nPos < 100) {
    				if(visited[nPos] == false) {
    					visited[nPos] = true;
    					q.offer(new Node(nPos, cnt + 1));	
    				}
    			}else if(nPos > 100){
    				break;
    			}
    		}
    	}
    	
    	
    	
    }
    
    
    
}

class Node{
	int pos;
	int cnt;
	public Node(int pos, int cnt) {
		this.pos=pos;
		this.cnt=cnt;
	}
}