[프로그래머스 고득점 Kit] 게임 맵 최단거리 자바 풀이 및 정답, 테스트케이스

테스트 케이스는 맨 아래에 있습니다.

문제요약)

- 주어진 맵에서 최단거리(칸 수) 리턴

 

주의점)

- 맵은 n * m 으로 이루어져 있고 서로 다를 수 있음

 

풀이)

1. 최단거리를 찾기에 BFS로 접근

2. 거리를 판단해야 하기에 주어진 map과 같은 visit 배열을 만들어서 거리를 표기

3. 4방향 탐색을 하면서 q에 넣는데 맵을 벗어나지 않게 처리, 이미 방문한곳을 안가게 처리

4. n과 m의 범위를 주의해야합니다. 저의 경우 이 부분을 헷갈려 시간을 낭비했습니다.

 

정답코드)

import java.util.*;

public class gameMinDistance {
	// 각 4방향을 보기 위한 dx, dy
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    public static int solution(int[][] maps) {
        int answer = 0;
        int width = maps[0].length;
        int height = maps.length;
        int[][] visit = new int[height][width];

        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(0, 0)); // 0,0시작
        visit[0][0] = 1; // 칸을 세는 거기 때문에 처음에 1부터 시작

        while (!q.isEmpty()) {
            Node position = q.poll();
            int curX = position.x;
            int curY = position.y;

            // 최종점 찾은 경우, 답을 못찾는 경우 종료
            if (curX == height-1 && curY == width-1) break;
            if (maps[height-1][width-1] == 0) break;

            // 4방향 탐구
            for (int i=0; i<4; i++) {
                int nx = curX + dx[i];
                int ny = curY + dy[i];

                // 오버 플로우 처리
                if (nx < 0 || nx > height-1 || ny < 0 || ny > width-1) {
                    continue;
                }
                // 막힌길, 이미 방문한 곳 제외
                if (maps[nx][ny] == 0 || visit[nx][ny] > 0) {
                    continue;
                }
                q.offer(new Node(nx, ny));
                visit[nx][ny] = visit[curX][curY] + 1; // 거리 1증가

            }
        }

        // 값이 있으면 넣고 없으면 -1
        if (visit[height-1][width-1] > 0) {
            answer = visit[height-1][width-1];
        } else {
            answer = -1;
        }

        return answer;
    }
}

class Node {
    int x;
    int y;

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

 

테스트케이스)

int[][] a1 = {{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}};
System.out.println(gameMinDistance.solution(a1)); // 11

int[][] a2 = {{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}};
System.out.println(gameMinDistance.solution(a2)); // -1

int[][] a3 = {{1,0,1},{1,0,1},{1,1,1}};
System.out.println(gameMinDistance.solution(a3)); // 5

int[][] a4 = {{1,0,1},{1,0,1},{1,1,0}};
System.out.println(gameMinDistance.solution(a4)); // -1

// n이 더 큰 경우(3x2)
int[][] a5 = {{1,1},{1,0},{1,1}};
System.out.println(gameMinDistance.solution(a5)); // 4

// m이 더 큰 경우(2x4)
int[][] a6 = {{1,1,1,1},{0,0,1,1}};
System.out.println(gameMinDistance.solution(a6)); // 5