[프로그래머스] Lv.2 : 게임 맵 최단거리 - 자바[Java]

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

프로그래머스

풀이

캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 구해야 하므로 BFS를 사용한다. BFS 시작 위치는 캐릭터의 시작 위치와 같다.

maps는 0과 1로만 이루어져 있으며 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타낸다. 캐릭터의 방문 여부를 나타내기 위해, 캐릭터가 방문한 칸은 maps에서 2 이상의 값으로 나타낸다. 즉, maps[x][y]는 (x, y)좌표(코드에서 maps는 (0,0)부터 시작하므로 실제로는 (x-1, y-1) 좌표)에 도착하기 위해 지나가야 하는 칸의 최솟값을 저장한다. 

 

로직

1. bfs() 함수를 호출한다.

2. n, m을 선언한다. 각각 maps의 행 개수, 열 개수를 의미한다.

3. 방향 배열 int[] dx, dy를 선언하고 초기화한다.

4. BFS에 사용할 큐를 선언한다.

5. 큐에 시작 위치(0,0)를 넣는다.

6. maps의 시작 위치(maps[0][0])에 2를 저장한다.

7. BFS를 수행한다.

	while(!q.isEmpty()) {
            int[] tmp = q.poll();
            int x = tmp[0];
            int y = tmp[1];
            
            if (x == n-1 && y == m-1) {
                cnt = maps[x][y] - 1; //2부터 카운트하였으므로 1을 빼줘야 함
                break;
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                //벽이 없는 자리이며 아직 방문하지 않은 칸이라면 해당 좌표를 큐에 넣고 maps 값 업데이트
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] == 1) {
                    q.add(new int[]{nx, ny});
                    maps[nx][ny] = maps[x][y] + 1;
                }
            }
        }

도착 지점을 만나면, 시작 지점에서 2부터 카운트를 시작했으므로 maps[x][y]에 1을 뺀 값을 cnt에 저장하고 반복문을 탈출한다.

벽이 없는 자리이며 아직 방문하지 않은 칸에 갈 수 있다면, 그 곳의 좌표를 큐에 넣고 그 곳의 maps 값을 업데이트 한다.

 

 

코드

import java.util.*;

class Solution {
    
    public int solution(int[][] maps) {
        
        int answer = bfs(maps);
        return answer;
    }
    
    public int bfs(int[][] maps) {
        
        int n = maps.length; //maps의 행 개수
        int m = maps[0].length; //maps의 열 개수
        
        //방향 배열
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        
        Queue<int[]> q = new LinkedList<>();
        
        q.add(new int[]{0, 0}); //시작 좌표를 큐에 넣는다
        //캐릭터가 방문한 칸은 maps에서 2 이상의 값으로 나타내므로 시작 좌표에서 카운트를 2부터 시작한다.
        maps[0][0] = 2;
        
        int cnt = -1;
        
        while(!q.isEmpty()) {
            int[] tmp = q.poll();
            int x = tmp[0];
            int y = tmp[1];
            if (x == n-1 && y == m-1) {
                cnt = maps[x][y] - 1; //2부터 카운트하였으므로 -1 을 해줘야 함
                break;
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                //벽이 없는 자리이며 아직 가지 않은 칸이라면 좌표를 큐에 넣고 maps 값 업데이트
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] == 1) {
                    q.add(new int[]{nx, ny});
                    maps[nx][ny] = maps[x][y] + 1;
                }
            }
        }
        
        return cnt;
    }
}