[프로그래머스(Programmers)][자바(java)] (Lv2) 게임 맵 최단거리 <찾아라 프로그래밍 마에스터>

 

programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

 

문제 풀이

*  BFS

import java.util.*;

public class Solution {

	class Path {
		int x, y, c;
		public Path(int x, int y, int c) {
			this.x = x;
			this.y = y;
			this.c = c;
		}
	}
    
	public int solution(int[][] maps) {
		int n = maps.length, m = maps[0].length;
		int x = 0, y = 0, c, nx, ny, nc = 0;
		int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 }, d;
		Queue<Path> q = new ArrayDeque<>(); Path p;
		boolean v[][] = new boolean[n][m];
		q.add(new Path(0, 0, 1));
		v[x][y] = true;
		while (!q.isEmpty()) {
			p = q.remove();
			x = p.x; y = p.y; c = p.c;
			for (d = 0; d < 4; ++d) {
				nx = x + dx[d]; ny = y + dy[d];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m || v[nx][ny] || maps[nx][ny] == 0)
					continue;
				nc = c + 1;
				if (nx == n - 1 && ny == m - 1)
					return nc;
				q.add(new Path(nx, ny, nc));
				v[nx][ny] = true;
			}
		}
		return -1;
	}

}