[백준 알고리즘] 1261번 알고스팟(Java) 문제 풀이

문제

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

문제에 대한 이해

그래프에 관련된 문제이다. 다만 아래에 설명에도 기재하겠지만, 일반적인 그래프문제는 아니였다. (내 기준에서는 그랬다.)

어떻게 풀 것인가?

처음에는 BFS로 접근했으나 벽을 어떻게 부술지에 대한 생각이 많았고, 몇 번 문제를 틀리다보니 문제에 대한 접근이 잘못되었다는 것을 알았다. 그래서 문제에 대하여 검색을 해보았는데.....

 

0-1 BFS라는 방식으로 푸는것이 가장 좋다고 하여 관련 알고리즘을 정리하였다.

https://superohinsung.tistory.com/162

[Algorithm] 0-1 BFS

이에 따라 벽(1)을 부수고 이동하는 경우는 가중치가 1만큼 증가하지만 방(0)으로 이동하는 경우는 가중치는 0이다. 방으로 이동하는 것이 벽으로 이동하는 것보다 가중치가 낮으므로 우선 순위가 높아야하기 때문에 덱의 가장 앞단(front)에 삽입하여 문제를 해결할 수 있었다.

 

시간복잡도

 O(V+E)

공간복잡도

O(NXM) 이다.

풀면서 놓쳤던점

골드 그래프 문제는 아직은 내게 너무 어렵다...

새로운 알고리즘에 대한 생각을 놓쳤다.

이 문제를 통해 얻어갈 것

0-1 BFS

내 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

// 백준알고리즘 1261번 알고스팟

public class Main {
    static int N, M;
    static int[][] map;

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

    public static int[] dy = {0, 1, 0, -1};
    // 1,1에서 시작하지만 map 기준에서는 0,0에서 시작
    // N,M은 N-1,M-1임
    // 0-1 BFS

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[M][N];
        for (int i = 0; i < M; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
        BFS();
    }

    private static void BFS() {
        LinkedList<int[]> que = new LinkedList<>();
        que.offer(new int[]{0, 0, 0});
        map[0][0] = -1;

        while (!que.isEmpty()) {
            int[] poll = que.poll();
            int x = poll[0];
            int y = poll[1];
            int z = poll[2];

            if (x == M - 1 && y == N - 1) {
                System.out.println(z);
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nowX = x + dx[i];
                int nowY = y + dy[i];

                if (nowX < 0 || nowY < 0 || M <= nowX || N <= nowY) {
                    continue;
                }

                if (map[nowX][nowY] == 0) {
                    que.addFirst(new int[]{nowX, nowY, z});
                } else if (map[nowX][nowY] == 1) {
                    que.offer(new int[]{nowX, nowY, z + 1});
                }
                map[nowX][nowY] = -1;
            }
        }
    }
}