[Java] leetcode 909. Snakes and Ladders

문제

https://leetcode.com/problems/snakes-and-ladders/description/

Snakes and Ladders - LeetCode

알아야 할 개념

• BFS

풀이

BFS 구현 문제이다. 풀이는 다음과 같다.

1. 주어진 번호를 좌표로 변환하는 메소드를 만든다. 
2. 주어진 좌표를 번호로 변환하는 메소드를 만든다. 
3. 주어진 조건에 따라 BFS 탐색을 구현한다. 
4. next 번호가 n x n 이상이면 탐색을 종료한다. 

BFS 로 지도 끝까지 탐색하면 탐색 횟수를 리턴하고 그렇지 않으면 -1 을 리턴.  중간에 사다리나 뱀을 만나면 이동해준다. 

내가 푼 로직 1번, 2번을 구현하는데 시간을 소비했다.

코드의 핵심은 좌표를 번호로, 번호를 좌표로 구현한 것이다. 

/*좌표를 번호로 리턴*/
	public int converToInt(int[]p){ 
        int r = p[0];
        int c = p[1];
        if(r % 2== 0)return (n-1-r)*n + c + 1;
        else return (n-1-r)*n + (n-1-c) + 1;
    }
    /*번호를 좌표로 리턴*/
    public int[] converToPos(int p){
        p-=1;
        int r = p/n;
        int c = p % n;
        if(r % 2 == 0)return new int[]{n-r-1, c};
        else return new int[]{n-r-1, n-c-1};
    }

코드

자바

class Solution {
    int n;
    public int snakesAndLadders(int[][] b) {
        n = b.length;
        if(n < 3)return 1;
        boolean v[] = new boolean[n*n+1];
        Queue<Integer> Q =new LinkedList<>();
        Q.offer(1);
        v[1] = true;
        int level = 1;
        while(!Q.isEmpty()){
            int size = Q.size();
            for(int i = 0 ;i < size; i++){
                int c = Q.poll();
                System.out.println(c + "lev:"+level+" ");
                
                for(int k = 1; k < 7; k++){
                    int nextN = c + k;
                    //System.out.println(nextN);
                    if(nextN >= n*n)return level;
                    int nt[] = converToPos(nextN);
                    int ntN = b[nt[0]][nt[1]];
                    if(ntN != -1 ){
                        if(ntN >= n*n)return level;
                        if(!v[ntN]){
                            Q.offer(ntN);
                            v[ntN] = true;
                        }
                    }else{
                        if(!v[nextN]){
                        v[nextN] = true;
                        Q.offer(nextN);
                        }
                    }
                }
            }
            level++;
        }
        return -1;
    }
    public int converToInt(int[]p){
        int r = p[0];
        int c = p[1];
        if(r % 2== 0)return (n-1-r)*n + c + 1;
        else return (n-1-r)*n + (n-1-c) + 1;
    }
    public int[] converToPos(int p){
        p-=1;
        int r = p/n;
        int c = p % n;
        if(r % 2 == 0)return new int[]{n-r-1, c};
        else return new int[]{n-r-1, n-c-1};
    }
}