게임 맵 최단거리

조건

1. 사용자는 무조건 map의 1,1에 위치하고, 상대팀 진영은 n,m에 위치한다.

2. 동서남북만 이동할 수 있고, 벽은 0, 갈수 있는길은 1이다.

 

전형적인 최단거리 탐색

최소값을 찾기 위하여 시간을 줄이기 위하여 bfs로 탐색하였다.

 

문제풀이 : BFS로 최단거리 탐색

 

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

public class Bfs {
    private static int[] dx = {-1,0,1,0};
    private static int[] dy = {0,1,0,-1};

    public class Point{

        int x;
        int y;
        int cnt;

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

    public int solution(int[][] maps) {
        int answer = -1;
        
        int lenX = maps.length;
        int lenY = maps[0].length;
        int[][] visit = new int[lenX][lenY];
        

        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(0,0,1));
        visit[0][0] = 1;
        while(!queue.isEmpty()){
            int x = queue.peek().x;
            int y = queue.peek().y;
            int cnt = queue.peek().cnt;
            
            queue.poll();
            if(x==lenX-1 && y == lenY -1){
                answer = cnt;
                break;
            }
            for(int i=0; i<4; i++){
                int xx = x + dx[i];
                int yy = y + dy[i];
                if(xx <0 || xx>= lenX || yy < 0 || yy >= lenY){
                    continue;
                }
                if(visit[xx][yy] == 0 && maps[xx][yy] == 1){
                    queue.add(new Point(xx, yy, cnt+1));
                    visit[xx][yy] = 1;
                }
            }

        }

        return answer;
    }

    public static void main(String[] args) {
        Bfs s3 = new Bfs();
        int[][] test = {{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(s3.solution(test));

    }
}

**

맵에서 queue에 push 할 때, visit 처리를 빼주면 시간초과가 발생한다.

중복으로 값이 들어갈 수 있기 때문에 ,push할 때 visit처리

 

 

DFS로 풀이하면 시간초과가 날 것 같아서 한번 해보았다.

public class Dfs {
    private static int[] dx = {-1,0,1,0};
    private static int[] dy = {0,1,0,-1};
    public int lenX;
    public int lenY;
    public int[][] visit;
    public int answer;

    public class Point{
        int x;
        int y;
        int cnt;
        public Point(int x, int y, int cnt){
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }


    public void dfs(int x, int y, int cnt, int[][] maps){
        if(x == lenX-1 && y == lenY-1){
            if(answer > cnt){
                answer = cnt;
                return;
            }
        }
        for(int i=0; i<4; i++){
            int xx = x + dx[i];
            int yy = y +dy[i];
            if(xx<0 || xx>=lenX || yy<0 || yy>=lenY){
                continue;
            }
            if(visit[xx][yy] == 0 && maps[xx][yy] ==1){
                visit[xx][yy] = 1;
                dfs(xx,yy,cnt+1, maps);
                visit[xx][yy] = 0;

            }
        }
    }


    public int solution(int[][] maps) {
        answer = 999999;
        lenX = maps.length;
        lenY = maps[0].length;
        visit = new int[lenX][lenY];
        visit[0][0] = 1;
        dfs(0,0,1,maps);


        System.out.println(answer);

        if(answer == 999999){
            answer = -1;
        }
        return answer;
    }


    public static void main(String[] args) {
        Dfs s3 = new Dfs();
        int[][] test = {{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}};
        s3.solution(test);

    }
}

**시간초과가 발생하였다. dfs로도 시간초과를 줄여서 할 수 있는 방법이 있을지 생각해봐야겠다.

 

 

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