[프로그래머스 - 자바(JAVA)] 43 : 게임 맵 최단 거리

목차

게임 맵 최단 거리

게임 맵 최단 거리 : Lv.2

---

▼ 문제

출처 : 프로그래머스 > 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 게임 맵 최단거리

▼ 내 풀이

• Point 라는 클래스를 만들어서 문제를 풀었다.
• 또한, 이동할 때마다 +1을 하여 이동 거리를 저장하는 dist 배열을 선언하고 Queue를 활용하여 문제에 접근했다.
• move 메서드는 dfs 알고리즘을 나타내며, 현재 위치를 queue에 넣는다.
• 이 때, dx, dy 배열을 통해서 다음 위치를 고려하고 다음 위치가 maps 안에 존재하고 다음 위치가 1의 값을 갖지 않는 조건에서 nextPoint를 생성하고 queue에 넣고 dist 배열 값에 1을 더한다.
• 위의 과정을 반복하면서 현재 위치가 목표 위치(끝)이면 check는 true가 되어 dist 배열의 목표 위치의 값을 반환한다.
• check 변수는 기본적으로 false로 되어 있어 만약 현재 위치가 목표 위치가 아니라면 -1을 반환한다.

[오답 코드]
import java.util.*;
class Solution {
    class Point {
        public int x;
        public int y;
        
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public Queue<Point> q = new LinkedList<>();
    public int[] dx = {-1, 1, 0, 0};
    public int[] dy = {0, 0, 1, -1};
    public int[][] dist;
    public boolean check;
    
    public int solution(int[][] maps) {
        check = false;
        dist = new int[maps.length][maps[0].length];
        dist[0][0] = 1;
        move(0,0, maps);
        return check ? dist[maps.length-1][maps[0].length-1] : -1;
    }
    
    public void move(int x, int y, int[][] maps) {
        Point p = new Point(x, y);
        q.add(p);
        maps[x][y] = 0;
        
        while(q.size() > 0) {
            Point tmp = q.poll();
            
            for(int i = 0; i < 4; i++) {
                int nextX = tmp.x + dx[i];
                int nextY = tmp.y + dy[i];
                
                if(nextX >= 0 && nextY >= 0 && nextX < maps[0].length && nextY < maps.length && maps[nextX][nextY] == 1) {
                    Point nextPoint = new Point(nextX, nextY);
                    q.add(nextPoint);
                    maps[nextX][nextY] = 0;
                    dist[nextX][nextY] = dist[tmp.x][tmp.y] + 1;
                    if(nextX == maps.length-1 && nextY == maps[0].length-1) {
            check = true;
        }
                }
                
            }
        }
        
    }
    
}

• 하지만, 위와 같이 작성했더니 매우 많은 실패를 얻었다.
  
• 아래는 수정된 코드이다.
• check 변수를 통해서 판단을 하여 리턴을 하지 않고 move 메서드가 -1을 반환하고 목적지에 도달할 경우에만 그 이동 경로를 반환하도록 수정했다.
• 또한, 이동할 수 있는 조건을 if문에 넣어 로직을 수행하는 것이 아닌 if 문 안에는 이동하지 못하는 조건을 넣고 contiue 하고 else를 통해서 이동할 수 있는 조건에서의 로직을 수행하도록 했다.
• 그리고 위의 코드에서는 조건을 and(&&)로 연결했기 때문에 모든 조건을 만족하는 경우만 고려했지만 다시 생각해보니 or(||)로 조건을 연결했어야 했다.

[수정 코드]
import java.util.*;
class Solution {
    class Point {
        public int x;
        public int y;
        
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public Queue<Point> q = new LinkedList<>();
    public int[] dx = {1, 0, -1, 0};
    public int[] dy = {0, 1, 0, -1};
    public int[][] dist;
    
    public int solution(int[][] maps) {
        dist = new int[maps.length][maps[0].length];
        dist[0][0] = 1;
        
        return move(0,0, maps);
    }
    
    public int move(int x, int y, int[][] maps) {
        Point p = new Point(x, y);
        q.add(p);
        maps[x][y] = 0;
        
        while(q.size() > 0) {
            Point tmp = q.poll();
            if(tmp.x == maps.length-1 && tmp.y == maps[0].length-1) {
                return dist[tmp.x][tmp.y];
            }
            
            for(int i = 0; i < 4; i++) {
                int nextX = tmp.x + dx[i];
                int nextY = tmp.y + dy[i];
                if(nextX < 0 || nextY < 0 || nextX > maps.length - 1 || nextY > maps[0].length - 1) {
                    continue;
                }
                if(maps[nextX][nextY] == 0) {
                    continue;
                } else {
                    Point nextPoint = new Point(nextX, nextY);
                    q.add(nextPoint);
                    maps[nextX][nextY] = 0;
                    dist[nextX][nextY] = dist[tmp.x][tmp.y] + 1;
                }
                
            }
        }
        return -1;
        
    }
    
}