[LeetCode- Part. 2] 5. 음식을 구하기위한 최단 경로 (+BFS)

 

package Part2.Q6;

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public static void main(String[] args) {
        char[][] grid = { { 'X', 'X', 'O', 'O', 'O', 'X' },
                { 'X', 'I', 'O', 'X', 'O', 'X' },
                { 'X', 'O', 'O', 'X', 'F', 'X' },
                { 'X', 'X', 'X', 'X', 'X', 'X' } };
        System.out.println(solve(grid));
    }
    static int n,m;
    static boolean [][] check;
    public static int solve(char[][] grid) {
        int[][] dirs= {{0,1}, {1,0}, {-1,0},{0,-1}};

        n= grid.length;
        m=grid[0].length;
        check = new boolean[n][m];
        int[] start=null;
        int[] end=null;

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]=='I') start= new int[]{i, j,0};
                if(grid[i][j]=='F') end= new int[]{i, j,0};
            }
        }
        if(end==null) return -1;

        Queue<int[]> q = new LinkedList<>();
        q.offer(start);
        int cnt=0;
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            //System.out.println(cur[0]+" "+cur[1]+" "+cur[2]);
            for (int[] dir : dirs) {
                int x=cur[0]+dir[0];
                int y=cur[1]+dir[1];
                int value=cur[2]+1;
                if(isValid(grid,x,y)){
                    if(x==end[0] && y==end[1]) return value;
                    check[x][y]=true;
                    q.offer(new int[]{x,y,value});
                }
            }
        }


        return -1;
    }
    public static boolean isValid(char[][] grid, int x, int y){
        if(x<0|| y<0||x>=n||y>=m ||grid[x][y]=='X'||check[x][y]) return false;
        return true;
    }
}

 

+세련된 풀이)

package realTest02;

import java.util.*;

public class A06_ShortestPathFood {

	public static void main(String[] args) {
		A06_ShortestPathFood a = new A06_ShortestPathFood();
		char[][] grid = { 
				{ 'X', 'X', 'X', 'X', 'X', 'X' }, 
				{ 'X', 'I', 'O', 'O', 'O', 'X' },
				{ 'X', 'O', 'O', 'F', 'O', 'X' }, 
				{ 'X', 'X', 'X', 'X', 'X', 'X' } };
		System.out.println(a.solve(grid));
	}

	int[][] dirs = new int[][] { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
	int m = 0, n = 0;

	public int solve(char[][] grid) {
		m = grid.length;
		n = grid[0].length;
		int count = 0;
		boolean[][] visited = new boolean[m][n];

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (grid[i][j] == 'I') {
					count = bfs(grid, i, j, visited);
					break;
				}
			}
		}
		return count;
	}

	public int bfs(char[][] grid, int x, int y, boolean[][] visited) {
		visited[x][y] = true;
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] { x, y, 0 });
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			for (int[] dir : dirs) {
				int x1 = cur[0] + dir[0];
				int y1 = cur[1] + dir[1];
//		        if(x1<0 || x1>= m || y1<0 || y1>=n|| visited[x1][y1] == true || grid[x1][y1] == 'X')
//		             continue;
				if (x1 >= 0 && y1 >= 0 && x1 < m && y1 < n && visited[x1][y1] != true && grid[x1][y1] != 'X') {
					if (grid[cur[0]][cur[1]] == 'F') {
						return cur[2];
					}
					visited[x][y] = true;
					q.offer(new int[] { x1, y1, cur[2] + 1 });

				}
			}
		}
		return -1;
	}
}