백준(BOJ) 1261 : 알고스팟 (JAVA)

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

1261번: 알고스팟

 

높은 정답률(현재 38%)에 비해 나에게는 정말 어려운 문제였다. 처음에는 DFS와 백트래킹을 이용해 풀어보려고 했으나 시간초과가 나왔다. 그도 그럴 것이 백트래킹의 시간복잡도는 O(2^N)인데, 여기서 주어진 N과 M의 범위를 생각했을 때 최악의 경우 2^10000번의 연산이 필요하다...;;;; 백트래킹을 사용해 아깝게(?) 통과하지 못한 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    private static int[] di = {-1, 1, 0, 0};
    private static int[] dj = {0, 0, -1, 1};
    private static int min = Integer.MAX_VALUE;
    private static int m;
    private static int n;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        
        boolean[][] maze = new boolean[n][m];
        
        for(int i = 0; i < n; i++) {
            char[] temp = br.readLine().toCharArray();
            
            for(int j = 0; j < m; j++) {
                maze[i][j] = temp[j] == '0' ? true : false;
            }
        }
        
        boolean[][] visited = new boolean[n][m];
        
        dfs(maze, visited, 0, 0, 0);
        
        System.out.println(min);
    }
 
    private static void dfs(boolean[][] maze, boolean[][] visited, int i, int j, int cnt) {
        visited[i][j] = true;
        
        if(cnt >= min) {
            return;
        }
        
        if(i == n - 1 && j == m - 1) {
            if(cnt < min) {
                min = cnt;
            }
            
            return;
        }
        
        for(int k = 0; k < 4; k++) {
            int nextI = i + di[k];
            int nextJ = j + dj[k];
            
            if(nextI >= 0 && nextI < n && nextJ >= 0 && nextJ < m && !visited[nextI][nextJ]) {
                if(maze[nextI][nextJ]) {
                    dfs(maze, visited, nextI, nextJ, cnt);
                } else {
                    dfs(maze, visited, nextI, nextJ, cnt + 1);
                }
                
                visited[nextI][nextJ] = false;
            }
        }
    }
}

 

백트래킹으로는 풀이가 불가능하다는 것을 깨닫고 BFS도 생각해보았으나, 한 번 방문된 곳이 다른 경우의 수에서 또 방문이 가능해야한다는 점을 해결하기 힘들었다. 사실 이 점 때문에 DFS 백트래킹을 처음 생각했던 것이었다. 모든 시점마다 boolean 배열을 추가해서 풀어볼까라는 생각도 해보았으나, 그 경우에는 메모리가 터질 것이었다. 나는 고뇌에 빠졌고, 결국 구글링을 통해 Deque를 이용하면 된다는 사실을 알아냈다. (우오오오오오오!!!)

특정 방에서 다음 방으로 넘어가는 단계에서, 4개의 후보 중 빈방으로 이동하는 것이 그 시점을 기준으로 가장 벽을 최소로 꺨 수 있는 방법일 것이다. 따라서 빈방으로 이동한 시점을 Deque의 앞쪽에 위치시키고(addFirst), 벽을 부순 시점을 Deque의 뒷쪽에 위치시킴으로써(addLast) 빈방으로 이동한 시점에 무조건 우선순위를 주게되면 굳이 visited에 대해 고민할 필요가 없어진다. 한 번 방문했을 때의 벽을 부순 횟수가 무조건 최소값이 되기 때문이다. 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    private static int[] di = {1, -1, 0, 0};
    private static int[] dj = {0, 0, 1, -1};
    
    public static void main(String[] args) throws Exception {
        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());
        
        boolean[][] isEmpty = new boolean[n][m];
        
        for(int i = 0; i < n; i++) {
            char[] temp = br.readLine().toCharArray();
            
            for(int j = 0; j < m; j++) {
                if(temp[j] == '0') {
                    isEmpty[i][j] = true;
                }
            }
        }
        
        int min = bfs(isEmpty, n, m);
        
        System.out.println(min);
    }
    
    private static int bfs(boolean[][] isEmpty, int n, int m) {
        boolean[][] visited = new boolean[n][m];
        visited[0][0] = true;
        Deque<Point> deque = new ArrayDeque<Point>();
        deque.offer(new Point(0, 0, 0));
        
        while(!deque.isEmpty()) {
            Point poll = deque.poll();
            int i = poll.getI();
            int j = poll.getJ();
            int cnt = poll.getCnt();
            
            if(i == n - 1 && j == m - 1) {
                return cnt;
            }
            
            for(int k = 0; k < 4; k++) {
                int nextI = i + di[k];
                int nextJ = j + dj[k];
                
                if(nextI >= 0 && nextJ >= 0 && nextI < n && nextJ < m && !visited[nextI][nextJ]) {
                    visited[nextI][nextJ] = true;
                    
                    if(isEmpty[nextI][nextJ]) {
                        deque.addFirst(new Point(nextI, nextJ, cnt));
                    } else {
                        deque.addLast(new Point(nextI, nextJ, cnt + 1));
                    }
                }
            }
        }
        
        return -1;
    }
 
    private static class Point {
        private int i;
        private int j;
        private int cnt;
        
        public Point(int i, int j, int cnt) {
            this.i = i;
            this.j = j;
            this.cnt = cnt;
        }
 
        public int getI() {
            return i;
        }
 
        public int getJ() {
            return j;
        }
 
        public int getCnt() {
            return cnt;
        }
    }
}

 

끝으로, 이 문제를 다 풀고 나니 알고리즘 분류가 '다익스트라 알고리즘'으로 되어있는 것을 알 수 있었다. 올바른 방법으로 풀었는지는 알 수 없으나;; 참고 삼아 공유해본다. 코드는 아래와 같으며, 다익스트라 알고리즘에 대해 참고했던 사이트 링크를 남긴다.  https://mattlee.tistory.com/50

<dijkstra의 최단="" 경로="" 알고리즘=""> 기본개념과 알고리즘</dijkstra의>

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {    
    private static int[] di = {1, 0, -1, 0};
    private static int[] dj = {0, 1, 0, -1};
    
    public static void main(String[] args) throws Exception {
        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());
        
        if(m == 1 && n == 1) {
            br.readLine();
            System.out.println(0);
            return;
        }
        
        boolean[][] visited = new boolean[n][m];
        short[][][][] wallInfo = new short[n][m][n][m];
        
        short[][] map = new short[n][m];
        
        for(int i = 0; i < n; i++) {
            char[] row = br.readLine().toCharArray();
            
            for(int j = 0; j < m; j++) {
                map[i][j] = (short) (row[j] - 48);
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                for(int k = 0; k < n; k++) {
                    for(int h = 0; h < m; h++) {
                        wallInfo[i][j][k][h] = 10000;
                    }
                }
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                for(int k = 0; k < 4; k++) {
                    int newI = i + di[k];
                    int newJ = j + dj[k];
                    
                    if(newI >= 0 && newI < n && newJ >= 0 && newJ < m) {
                        wallInfo[i][j][newI][newJ] = map[newI][newJ];
                    }
                }
            }
        }
        
        visited[0][0] = true;
        short[][] distance = wallInfo[0][0];
        
        while(true) {
            int minI = Integer.MAX_VALUE;
            int minJ = Integer.MAX_VALUE;
            int min = Integer.MAX_VALUE;
            
            for(int a = 0; a < n; a++) {
                for(int b = 0; b < m; b++) {    
                    if(!visited[a][b] && distance[a][b] < min) {
                        min = distance[a][b];
                        minI = a;
                        minJ = b;
                    }
                }
            }
            
            if(minI == n - 1 && minJ == m - 1) {
                break;
            }
            
            visited[minI][minJ] = true;
            
            for(int a = 0; a < n; a++) {
                for(int b = 0; b < m; b++) {
                    if(!visited[a][b]) {
                        if(distance[a][b] > distance[minI][minJ] + wallInfo[minI][minJ][a][b]) {
                            distance[a][b] = (short) (distance[minI][minJ] + wallInfo[minI][minJ][a][b]);
                        }
                    }                
                }
            }
        }
        
        System.out.println(distance[n - 1][m - 1]);
    }
}