Kim Ji Soo :blush:

즐겨라 👊

1 분 소요

📁 [Lv2_1844] 게임 맵 최단거리 

import java.util.*;

class Solution{
  // 좌표, cost 값
  public class Node{
    int x;
    int y;
    int cost;

    public Node(int x, int y, int cost){
      this.x = x;
      this.y = y;
      this.cost = cost;
    }
  }

  int[] dx = {0,0,1,-1};
  int[] dy = {1,-1,0,0};
  int n,m;
  boolean[][] check;

  public int solution(int[][] maps){
    int answer = 0;

    // 범위
    n = maps.length;
    m = maps[0].length;
    check = new boolean[n][m];

    answer = bfs(maps,0,0);


    return answer;
  }

  public int bfs(int[][] maps, int x, int y){
    // Queue 생성
    Queue<Node> q = new LinkedList<Node>();
    // 처음 값 넣기 ( 가격은 1 )
    q.offer(new Node(x,y,1));
    // 방문 처리
    check[y][x] = true;

    // q가 빌때까지 진행
    while(!q.isEmpty()){
      // 하나 꺼내기
      Node node = q.poll();

      // 만약 도착하면 끝
      // 어차피 bfs로 진행하면 최솟값이다
      if(node.x == m-1 && node.y == n-1) return node.cost;

      // 좌표 이동
      int nx = 0;
      int ny = 0;
      for(int i=0; i<4; i++){
        nx = node.x + dx[i];
        ny = node.y + dy[i];

        // map을 벗어나거나 벽을 만나거나 이미 방문한 경우 통과
        if(nx < 0 || ny < 0 || nx >= m || ny >= n || check[ny][nx] || maps[ny][nx] == 0) continue;

        // 방문처리
        check[ny][nx] = true;
        // 큐에 추가
        q.offer(new Node(nx, ny, node.cost+1));
      }

    }
    // 만약 도착할 수 없으면 -1
    return -1;
  }
}

🤔 나의 생각

최단 거리를 구하는 문제이다.
처음에 dfs로 풀었다가 효율성 부분에서 탈락..
최단 거리 구하는 문제는 앞으로 무조건 bfs로 푸는 걸로! 가장 기본적인 문제이다. 중간에 넘어가야할 부분과 기저조건만 잘 체크하면 쉽게 풀 수 있다.

참고