[프로그래머스] 게임 맵 최단거리

문제 링크

• https://programmers.co.kr/learn/courses/30/lessons/1844

문제 요약

• (1,1) 에서 (n,m) 까지 가는 최단 거리를 구한다

풀이 흐름

• BFS 문제. 이번 회차에 내 캐릭터가 (x, y) 위치에 있다면 다음 회차에는 (x, y)를 기준으로 상, 하, 좌, 우로 이동할 수 있다. 이동할 수 있는 위치가 map을 벗어나지 않고 벽으로 가로막혀 있지 않다면 그 칸으로 이동한다. 위 과정을 반복한다.
• 대신 이제까지 몇칸을 이동했는지 알아야 하니까 (nx, ny) 위치까지 이동한 칸의 수는 (x, y) 위치까지 이동한 칸 수 + 1
• (x, y) 가 (n, m)이 되면 해당 칸까지 이동한 거리를 리턴 한다.

---

코드
풀이 언어 : JAVA

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

	public void bfs(int[][] maps, Queue<int[]> q) {
		while(!q.isEmpty()) {
			int[] pos = q.poll();
			int x = pos[0];
			int y = pos[1];
			
			if(x == n-1 && y == m-1) {
				break;
			}
			
			for(int[] d : dirs) {
				int nx = x + d[0];
				int ny = y+ d[1];
				if(0 <= nx && nx < n && 0 <= ny && ny < m
					&& maps[nx][ny] == 1 && visited[nx][ny] == 0) {
					q.add(new int[] { nx, ny });
					visited[nx][ny] = visited[x][y] + 1;
				}
			}
		}
	}
	public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        
        Queue<int[]> q = new LinkedList<int[]>();
        q.add(new int[] { 0, 0 });
        visited[0][0] = 1;
        bfs(maps, q);
        
        if(visited[n-1][m-1] == 0) {
        	return -1;
        }
        
        return visited[n-1][m-1];
    }