[자바] 프로그래머스 - 게임 맵 최단거리 (BFS) / 유사문제

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

프로그래머스

정답률 52%의 어렵지 않은 bfs 문제입니다.

 

좌표 값(0,0) 에서 좌표 값(n, m)에 도달할 수 없다면 -1을 출력, 도달할 수 있다면 몇 번을 이동해야 최단으로 도착하는지 출력을 하면 됩니다.

 

문제 접근 방법

저 같은 경우 이 문제를 보고나서 다음과 같은 방법으로 풀이를 생각했습니다.

 

1. 목적지까지의 이동 거리를 최단으로 하려면 몇 번을 구해야 하는지에 대해서

   - 최단까지의 이동을 하려면 먼저 완전 탐색을 해야된다.

      - 그래프를 완전 탐색하기 위해서 dfs 혹은 bfs로 접근해야 한다.

 

2. dfs와 bfs 중 무엇을 선택할지에 대해서 

   - '최단 거리' 라는 말에 집중을 했습니다. "깊이 우선이 아닌, 너비 우선 탐색인 bfs를 통해서 조금 더 효율적으로 구할 수 있겠구나" 라고 생각했습니다.

 

   - '최단 거리' 라는 워딩이 나오면 dfs로 풀리는 문제도 있지만, 백준에서 dfs로 이런 유형을 풀 때 시간초과로 많이 골치 아팠던 경험이 있어서 이런류의 문제(미로찾기, 최단거리 등등)는 보통 너비우선탐색인 bfs로 푸는 편입니다.

 

 

 

해결하기

import java.util.LinkedList;
import java.util.Queue;

class Solution {
   static int[][] map;
    static int[][] visited;
    static int answer;
    static boolean canNotDone = true;
    static int[][] pos = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

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

        map = maps;
        visited = new int[map.length][map[0].length];

        bfs();
        answer = visited[maps.length - 1][maps[0].length - 1];

        if (answer == 0) {
            answer = -1;
        }

        return answer;
    }

    public static void bfs() {
        visited[0][0] = 1;
        Queue<int[]> q = new LinkedList();
        q.add(new int[]{0, 0});

        while (!q.isEmpty()) {
            answer++;
            int[] now = q.poll();
            int nowX = now[0];
            int nowY = now[1];

            if (nowX == map.length - 1 && nowY == map[0].length - 1) {
                canNotDone = false;
            }

            for (int i = 0; i < pos.length; i++) {
                int nx = nowX + pos[i][0];
                int ny = nowY + pos[i][1];

                if (nx >= 0 && nx < map.length && ny >= 0 && ny < map[0].length && map[nx][ny] == 1 && visited[nx][ny] == 0) {
                    visited[nx][ny] = visited[nowX][nowY] + 1;
                    q.add(new int[]{nx, ny});
                }
            }
        }
    }
}

 

 

 

유사 문제

백준 2178번, 미로 탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색