공부 203일차: 백준 1261번 알고스팟 자바 java

1261 알고스팟

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

1261번: 알고스팟

 

 

 

---

백준 1261번 문제 알고스팟

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초 (추가 시간 없음)	128 MB	32738	14014	9530	41.875%

문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

제한

 

예제 입력 1

3 3
011
111
110

예제 출력 1

3

예제 입력 2

4 2
0001
1000

예제 출력 2

0

예제 입력 3

6 6
001111
010000
001111
110001
011010
100010

예제 출력 3

2

 

 

 

 

---

과정 생각해보기 & 오답

---

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, m;
    static int min = Integer.MAX_VALUE;
    static int[][] matrix;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    
    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());
        matrix = new int[m][n];
        visited = new boolean[m][n];
        
        for(int i = 0; i < m; i++) {
            String str = br.readLine();
            for(int j = 0; j < n; j++) {
                matrix[i][j] = str.charAt(j)-'0';
            }
        }
    
        bfs();
        System.out.println(min);
    }
 
    static void bfs() {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(0, 0, 0));    //    (1,1)자리에서 시작
        
        while(!q.isEmpty()) {
            Point now = q.poll();
            visited[now.x][now.y] = true;
            
            if(now.x == m-1 && now.y == n-1) {
                min = Math.min(min, now.count);
            }
            
            for(int i = 0; i < 4; i++) {    // 상하좌우
                int X = now.x + dx[i];
                int Y = now.y + dy[i];
                
                if(X < 0 || X > m-1 || Y < 0 || Y > n-1) {
                    continue;
                }
                
                if(!visited[X][Y] && matrix[X][Y] == 0) {    // 그냥 넘어갈 수 있음
                    q.add(new Point(X, Y, now.count));
                }
                
                if(!visited[X][Y] && matrix[X][Y] == 1) {    // 벽 -> 뚫어야 함
                    q.add(new Point(X, Y, now.count+1));
                }
            }
        }
    }
    
    static class Point{
        int x;
        int y;
        int count;
        
        Point(int x, int y, int count){
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
}

메모리 초과가 뜬 코드

이 문제처럼 조건을 줘서 끊어보려고 했는데, 그러면 최소값 갱신이 되지 않았다

그래서 검색해보니 일반 Queue를 사용하면 안 되고, 우선순위큐를 써야 한다고 한다

 

하지만.. 난 덱을 썼다..

이 블로그에 매우 상세하게 설명되어 있음!

요약하자면 양쪽으로 데이터를 넣을 수 있는 덱을 이용해서 앞으로 넣는 게 우선순위인지, 뒤로 넣는 게 우선순위인지 알려주는 것이다

 

벽보다 벽이 없는 쪽을 먼저 가는 것이 최소값을 만족하므로, 이쪽을 우선순위로 둔디

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, m;
    static int[][] matrix;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    
    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());
        matrix = new int[m][n];
        visited = new boolean[m][n];
        
        for(int i = 0; i < m; i++) {
            String str = br.readLine();
            for(int j = 0; j < n; j++) {
                matrix[i][j] = str.charAt(j)-'0';
            }
        }
    
        bfs();
    }
 
    static void bfs() {
        Deque<Point> deque = new LinkedList<>();
        deque.addLast(new Point(0, 0, 0));    //    (1,1)자리에서 시작
        visited[0][0] = true;
        
        while(!deque.isEmpty()) {
            Point now = deque.pollLast();
//            visited[now.x][now.y] = true;    // 순서가 달라지는 등 필요할 때 아니면 쓰지 않기
            
            if(now.x == m-1 && now.y == n-1) {
                System.out.println(now.count);
                return;    // 덱으로 우선순위를 설정했으므로 min 변수를 설정할 것 없이 바로 끝내면 된다
            }
            
            for(int i = 0; i < 4; i++) {    // 상하좌우
                int X = now.x + dx[i];
                int Y = now.y + dy[i];
                
                if(X < 0 || X > m-1 || Y < 0 || Y > n-1) {
                    continue;
                }
                
                if(!visited[X][Y] && matrix[X][Y] == 0) {    // 그냥 넘어갈 수 있음
                    visited[X][Y] = true;
                    deque.addLast(new Point(X, Y, now.count));
                }
                
                if(!visited[X][Y] && matrix[X][Y] == 1) {    // 벽 -> 뚫어야 함
                    visited[X][Y] = true;
                    deque.addFirst(new Point(X, Y, now.count+1));
                }
            }
        }
    }
    
    static class Point{
        int x;
        int y;
        int count;
        
        Point(int x, int y, int count){
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
}

 

 

 

---

코드 짜다가 메모리 관련 문제와 부딪치면 많이 어렵다..