[Level 2] 게임 맵 최단거리

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

프로그래머스

당연히 DFS 문제 아닌가?

class Solution {
    public static int answer = Integer.MAX_VALUE;

    public int solution(int[][] maps) {

        boolean[][] visited = new boolean[maps.length][maps[0].length];

        DFS(0, 0, maps, 1, visited);

        if(answer== Integer.MAX_VALUE)
            return -1;

        return answer;
    }

    public void DFS(int y, int x, int[][] maps, int cnt, boolean[][] visited) {

        visited[y][x] = true;

        if (y == maps.length - 1 && x == maps[0].length - 1) {
            if (answer > cnt)
                answer = cnt;
        }

        // ->
        if (x + 1 < maps[0].length && maps[y][x + 1] == 1 && visited[y][x + 1] == false)
            DFS(y, x + 1, maps, cnt + 1, visited);
        // <-
        if (x - 1 >= 0 && maps[y][x - 1] == 1 && visited[y][x - 1] == false)
            DFS(y, x - 1, maps, cnt + 1, visited);
        // ▼
        if (y + 1 < maps.length && maps[y + 1][x] == 1 && visited[y + 1][x] == false)
            DFS(y + 1, x, maps, cnt + 1, visited);
        // ▲
        if (y - 1 >= 0 && maps[y - 1][x] == 1 && visited[y - 1][x] == false)
            DFS(y - 1, x, maps, cnt + 1, visited);

        visited[y][x] = false;
    }
}

정답으로 갈 수 있는 길을 모두 한 번씩 해보면서 작은 cnt 일 때마다 갱신

효율성 1234 다 탈락

 

그러면 한번 정답까지 간 길 이 이미 있고

멍청하게 돌아오다가 옛날 정답 기존 길을 밟으면

그 길은 끝까지도 안 가보고 탈락시키자

class Solution {
    public int solution(int[][] maps) {

        boolean[][] visited = new boolean[maps.length][maps[0].length];
        int[][] count = new int[maps.length][maps[0].length];

        DFS(0, 0, maps, 1, visited, count);

        if (count[maps.length - 1][maps[0].length - 1] == 0)
            return -1;
        else
            return count[maps.length - 1][maps[0].length - 1];

    }

    public void DFS(int y, int x, int[][] maps, int cnt, boolean[][] visited, int[][] count) {

        if (count[y][x] == 0)
            count[y][x] = cnt;

        else if (count[y][x] <= cnt)
            return;

        else
            count[y][x] = cnt;

        visited[y][x] = true;

        // ->
        if (x + 1 < maps[0].length && maps[y][x + 1] == 1 && visited[y][x + 1] == false)
            DFS(y, x + 1, maps, cnt + 1, visited, count);
        // ▼
        if (y + 1 < maps.length && maps[y + 1][x] == 1 && visited[y + 1][x] == false)
            DFS(y + 1, x, maps, cnt + 1, visited, count);
        // <-
        if (x - 1 >= 0 && maps[y][x - 1] == 1 && visited[y][x - 1] == false)
            DFS(y, x - 1, maps, cnt + 1, visited, count);
        // ▲
        if (y - 1 >= 0 && maps[y - 1][x] == 1 && visited[y - 1][x] == false)
            DFS(y - 1, x, maps, cnt + 1, visited, count);

        visited[y][x] = false;
    }
}

효율성 13 탈락

왜 bfs로 풀어야 하지?

https://school.programmers.co.kr/questions/18867

프로그래머스

import java.util.*;

class Solution {
    public class Node {
        int y;
        int x;
        int count;

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

    public int solution(int[][] maps) {

        boolean[][] visited = new boolean[maps.length][maps[0].length];
        Queue<Node> queue = new LinkedList<>();

        return bfs(maps, visited, queue, new Node(0, 0, 1));
    }

    public int bfs(int[][] maps, boolean[][] visited, Queue<Node> queue, Node start) {

        queue.add(start);
        visited[start.y][start.x] = true;

        while (!queue.isEmpty()) {
            Node tmp = queue.remove();

            if(tmp.y == maps.length-1 && tmp.x == maps[0].length-1)
                return tmp.count;


            if (tmp.x + 1 < maps[0].length && maps[tmp.y][tmp.x + 1] == 1 && visited[tmp.y][tmp.x + 1] == false) {
                visited[tmp.y][tmp.x + 1] = true;
                queue.add(new Node(tmp.y,tmp.x+1,tmp.count+1));
            }
            if (tmp.y + 1 < maps.length && maps[tmp.y + 1][tmp.x] == 1 && visited[tmp.y + 1][tmp.x] == false) {
                visited[tmp.y + 1][tmp.x] = true;
                queue.add(new Node(tmp.y+1,tmp.x,tmp.count+1));
            }
            if (tmp.x - 1 >= 0 && maps[tmp.y][tmp.x - 1] == 1 && visited[tmp.y][tmp.x - 1] == false) {
                visited[tmp.y][tmp.x - 1] = true;
                queue.add(new Node(tmp.y,tmp.x-1,tmp.count+1));
            }
            if (tmp.y - 1 >= 0 && maps[tmp.y - 1][tmp.x] == 1 && visited[tmp.y - 1][tmp.x] == false) {
                visited[tmp.y - 1][tmp.x] = true;
                queue.add(new Node(tmp.y-1,tmp.x,tmp.count+1));
            }

        }

        return -1;
    }
}

열심히 bfs