[백준 Gold 4] 1261 알고스팟 - Java

문제링크 : https://www.acmicpc.net/problem/1261

1261번: 알고스팟

 

접근 과정 : 

• 결국 목적지까지, 벽을 최소한으로 뚫고 가야하는 문제이다.
• 일반적으로 벽을 뚫은 횟수를 포함한 BFS를 생각했다.
• 우선순위큐로 벽을 뚫은 횟수가 가장 적은 경우를 꺼내면서 BFS 탐색을 실시했다.
• 벽을 만났을 때는, 벽을 뚫은 횟수+1 해서 우선순위 큐에 집어넣고, 벽이 아니면 현재 벽을 뚫은 횟수를 집어넣는다.
• 이렇게 하면 쉽게 해결할 수 있다.

 

• ++++ 해결후에, 다른사람의 코드를 보니 덱을 사용했더라!!!
• BFS를 사용해서 큐에 새로운 위치와 횟수를 집어넣을 때, 횟수는 최대 1밖에 차이나지 않는다!!
• 이를 고려해서, 벽을 만나면 덱의 맨 뒤에 집어넣고, 벽이 아니면 덱의 맨 앞에 집어넣는다.!!
• 이러면 우선순위 큐 내부의 연산을 하지 않아도 된다!!!

 

소스 코드 및 결과 :

package BOJ;

/* 
    알고스팟
	
    우선순위 큐 활용!!

*/

import java.io.*;
import java.util.*;

public class BOJ1261_copy {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        char[][] maze = new char[N][M];

        for (int i = 0; i < N; i++) {
            maze[i] = br.readLine().toCharArray();
        }

        boolean[][] visit = new boolean[N][M];
        visit[0][0] = true;
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> {
            return a[2] - b[2];
        });
        queue.add(new int[] { 0, 0, 0 });

        while (!queue.isEmpty()) {

            int[] now = queue.poll();

            if (now[0] == N - 1 && now[1] == M - 1) {
                System.out.println(now[2]);
                break;
            }

            for (int i = 0; i < 4; i++) {

                int x = now[0] + move[i][0];
                int y = now[1] + move[i][1];

                if (x < 0 || x >= N || y < 0 || y >= M || visit[x][y]) {
                    continue;
                    
                }

                visit[x][y] = true;
                if (maze[x][y] == '1') {
                    queue.add(new int[] { x, y, now[2] + 1 });
                } else {
                    queue.add(new int[] { x, y, now[2] });
                }

            }

        }

    }

    static int[][] move = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
}

 

 

package BOJ;

/* 
    알고스팟
    
    덱 사용
*/

import java.io.*;
import java.util.*;

public class BOJ1261 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        char[][] maze = new char[N][M];

        for (int i = 0; i < N; i++) {
            maze[i] = br.readLine().toCharArray();
        }

        boolean[][] visit = new boolean[N][M];
        visit[0][0] = true;
        Deque<int[]> deque = new ArrayDeque<>();
        deque.add(new int[] { 0, 0, 0 });

        while (!deque.isEmpty()) {

            int[] now = deque.pollFirst();

            if (now[0] == N - 1 && now[1] == M - 1) {
                System.out.println(now[2]);
                break;
            }

            for (int i = 0; i < 4; i++) {

                int x = now[0] + move[i][0];
                int y = now[1] + move[i][1];

                if (x < 0 || x >= N || y < 0 || y >= M || visit[x][y]) {
                    continue;

                }

                visit[x][y] = true;
                if (maze[x][y] == '1') {
                    deque.addLast(new int[] { x, y, now[2] + 1 });
                } else {
                    deque.addFirst(new int[] { x, y, now[2] });
                }

            }

        }

    }

    static int[][] move = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
}

 

P.S 

덱을 사용해서, 우선순위 큐의 연산을 수행하지 않으니 확실히 시간적으로 줄어든 것을 볼 수 있다.

++ java 8에 비해서 java 11이 우선순위 큐의 성능을 높였다고 들은 것 같은데.. 이번에 실제로 본 것 같다!!

     우선순위 큐를 활용한 풀이에서 java 8과 java 11 의 시간이 거의 2배이다!!