프로그래머스) 1844. 게임 맵 최단 거리 (자바)

게임 맵 최단 거리

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

문제 :

• 상대 팀 진영에 도착할 수 있는 최단 거리를 출력하라
• 이차원 맵 maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리
• n과 m은 서로 같을 수도, 다를 수도 있음(정사각형 아님)

예시 1

• maps [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]
• answer 11

  예시 2

• maps [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]
• answer
  -1

bfs

특징

• x,y를 Point class로 묶음
• 상하좌우 검사용 배열 d
• 가로와 세로의 길이가 다를 수 있음

• visited 배열에 누적 후 마지막 값 반환
  ``` import java.util.*; class Point { int x; int y; public Point(int x, int y) { this.x = x; this.y = y; } } class Solution { //상하좌우 int[][] d = { {1,0}, {-1,0}, {0,1}, {0,-1} }; int lenx; int leny;

  public int solution(int[][] maps) { // x와 y가 바뀜 lenx = maps.length ; leny = maps[0].length;

   Queue<Point> q = new LinkedList<>();
   q.add(new Point(0,0));// 시작점을 큐에 넣는다.
   int[][] visited = new int[lenx][leny];
   visited[0][0] = 1;
   bfs(q, visited, maps);
   int answer = visited[lenx-1][leny-1]; //*** 누적한 마지막 값을 반환
   if(answer == 0) {
       return -1;
   }
   return answer;  }
  

  public void bfs(Queue q, int[][] visited, int[][] maps) { while(!q.isEmpty()) {

       Point p = q.poll();
       if(p.x == lenx-1 && p.y == leny-1) {
           return;
       }
       for(int i=0; i<4; i++){
           int tmp_x = p.x + d[i][0];
           int tmp_y = p.y + d[i][1];
          if(tmp_x < 0 ||  tmp_y < 0 || tmp_x >= lenx || tmp_y >= leny 
             || visited[tmp_x][tmp_y]  > 1  || maps[tmp_x][tmp_y] == 0) {
              continue;
          }
          visited[tmp_x][tmp_y] = visited[p.x][p.y]+1; // ***visited에 값 누적
          if(tmp_x == lenx-1 && tmp_y == leny-1) {
               return;
           }
           q.add(new Point(tmp_x,tmp_y));   
                       
       }
          
          
   }
  

  }

} ```