[JAVA]389480 완전 범죄

[JAVA]389480 완전 범죄

 📚 문제  

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

프로그래머스

 

🔍 아이디어  

bfs를 통한 완전 탐색형 구현.

but 확인했던것은 재확인하지 않도록 해야 시간 초과를 면할 수 있다.

 

📝 풀이 

import java.util.*;

class Solution {
   public int solution(int[][] info, int n, int m) {
        int min = Integer.MAX_VALUE;
        boolean[][] saved;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{0, 0});
        for (int[] in : info) {
            int now = queue.size();
            saved = new boolean[n][m];

            for (int j = 0; j < now; j++) {
                int[] poll = queue.poll();
                int nowA = poll[0];
                int nowB = poll[1];
                int mvA = nowA + in[0];
                int mvB = nowB + in[1];
                if (mvA < n && !saved[mvA][nowB]) {
                    queue.add(new int[]{mvA, nowB});
                    saved[mvA][nowB] = true;
                }
                if (mvB < m && !saved[nowA][mvB]) {
                    queue.add(new int[]{nowA, mvB});
                    saved[nowA][mvB] = true;
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            min = Math.min(poll[0], min);
        }
        return (min == Integer.MAX_VALUE) ? -1 : min;
    }

}