[PRO] 게임 맵 최단거리 | Java

문제

프로그래머스 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 게임 맵 최단거리

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

프로그래머스

• 알고리즘 분류 : 너비 우선 탐색(BFS)

 

 

풀이 과정

자바 풀이

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int answer = 0;
        int[][] visited = new int[maps.length][maps[0].length];
        // 방문 여부를 확인하기 위한 maps와 동일한 크기의 이차원 배열 생성
		
		bfs(maps, visited);
		answer = visited[maps.length-1][maps[0].length-1];
        // 오른쪽 하단 위치가 최종 위치이므로
        // visited의 해당 위치에 적힌 숫자가 최단거리
        // 만약 0이면 갈 수 없는 경우이므로 -1
		if(answer==0)
			answer = -1;
        return answer;
    }
    
	static void bfs(int[][] maps, int[][] visited) {
		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};
        // 상하좌우 네 가지 방향에 대해 탐색 
		
		visited[0][0] = 1;
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[]{0, 0});
        // queue에 처음 위치인 (0, 0) 추가 
		
		while(!q.isEmpty()) {
			int[] rm = q.remove();
			int x = rm[0];
			int y = rm[1];
			
			for(int d=0; d<4; d++) {
				int nx = x + dx[d];
				int ny = y + dy[d];
				
                // 네 가지 방향으로 이동하는 경우를 탐색하는데 
                // 범위 벗어나면 continue
				if(nx<0 || nx>=maps.length || ny<0 || ny>=maps[0].length)
					continue;
				
                // 간 적 없고, 벽이 없어서 갈 수 있는 위치면
                // 이전 까지의 거리 + 1해서 방문 기록 남기고, q에 추가 
				if(visited[nx][ny]==0 && maps[nx][ny]==1) {
					visited[nx][ny] = visited[x][y] + 1;
					q.add(new int[] {nx, ny});
				}
			}
		}
	}
}

• BFS/DFS를 파이썬으로만 풀다가 자바로는 처음 풀었는데, queue 사용법에서 조금 헤맸지만, 나머지는 거의 유사했다.
• 자바로 dfs/bfs 문제 조금 더 풀어보면서 완전히 익숙해져야 겠다.