[백준 1261번] 알고스팟 - (Java/python)

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

1261번: 알고스팟

 

Idea

문제를 보면 그래프 문제인것은 바로 알 수 있다. 

시작점 (1,1) 에서 목적지(n,m) 으로 이동하려고 할때 벽을 부수는 최소 횟수를 구하려고 한다.

운이 좋으면 벽을 하나도 안부수고 목적지 까지 갈 수 있고, 아니면 벽을 1개 이상 부수어야 할 수도 있다.

 

이 문제는 두가지 풀이로 풀 수있다.

첫번째 풀이는 큐를 두개 사용하는 것이고, 두번째 풀이는 덱을 사용하는 것이다.

 

첫번째 풀이부터 보면 

우선 벽을 안부수고 갈수 있는 경우를 다 확인한뒤에 벽을 1개 부수고 갈수있는 곳을 다 구해주고 그다음 벽을 2개 부수고 갈수있는 곳을 다 구해주고.. 이런식으로 풀수 있다. 따라서 첫번째 큐에는 벽을 0개 부수고 이동할 수 있는 경우에 대해서 다 넣어준다. 

만약에 벽을 마주치면 벽을 부수어야 갈수 있는 곳이므로 두번째 큐에 넣어준다.

 

그래서 첫번째 큐에 들어있는 모든 경우에 대해 distance (몇개를 부수어서 갈수있는지 저장) 배열 값을 업데이트 해주고 첫번째 큐가 비게되면 벽을 안부수고 갈수 있는 모든 경우를 확인한 것이므로 첫번째 큐 변수에 두번째 큐 변수 값을 넣어준다.

그러면 이제 첫번째 큐는 벽을 1번 부수고 이동할수 있는 모든 위치를 확인할수 있게 된다. 

 

두번째 풀이는 덱을 사용하는 것이다. 덱의 경우 양쪽에 값을 넣거나 뺄수 있으므로 현재 위치에서 벽을 안부수고 갈수 있는곳은 앞에 넣어서 먼저 처리할수있게 해주고 벽이나오면 맨뒤에 넣어서 나중에 처리할 수 있게 해준다.

 

두 풀이다 중요한 것은 가장 먼저 벽을 적게 부수는것 부터 처리를 해준다는 것이다.

---

코드

Java

 

큐 2개를 사용한 풀이

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        sc.nextLine();

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

        int[][] arr = new int[n][m];
        int[][] distance = new int[n][m];
        boolean[][] visited = new boolean[n][m];

        for(int i=0; i<n; i++){
            String s = sc.nextLine();
            for(int j=0; j<m; j++){
                arr[i][j] = s.charAt(j) -'0';
            }
        }

        Queue<Node> q_now = new LinkedList<>();
        Queue<Node> q_next = new LinkedList<>();
        q_now.add(new Node(0,0));

        distance[0][0] = 0;
        visited[0][0] = true;

        while(!q_now.isEmpty()){
            Node node = q_now.poll();
            int x = node.x;
            int y = node.y;
            for(int i=0; i<4; i++){
                int nx = x+dx[i];
                int ny = y+dy[i];
                if(nx>=0 && ny>=0 && nx<n && ny<m){
                    if(!visited[nx][ny]){
                        if(arr[nx][ny]==0){ // 벽이 없는 곳으로 이동 (벽을 부수지 않고 이동)
                            q_now.add(new Node(nx,ny));
                            visited[nx][ny] = true;
                            distance[nx][ny] = distance[x][y];
                        }else{ // 벽을 부수고 이동
                            q_next.add(new Node(nx,ny));
                            visited[nx][ny] = true;
                            distance[nx][ny] = distance[x][y]+1;
                        }
                    }
                }
            }
            if(q_now.isEmpty()){
                q_now = q_next;
                q_next = new LinkedList<>();
            }
        }


        System.out.println(distance[n-1][m-1]);

    }
}

class Node{
    int x,y;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

 

덱을 사용한 풀이

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 *  알고스팟 다른 풀이
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(); // 가로
        int n = sc.nextInt(); // 세로
        sc.nextLine(); // enter 제거

        int[][] arr = new int[n][m];
        int[][] dist = new int[n][m]; // 몇개의 벽을 부수었는지 저장.

        for(int i=0; i<n; i++){
            Arrays.fill(dist[i],-1);
        }

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

        for(int i=0; i<n; i++){
            String str = sc.nextLine();
            for(int j=0; j<m; j++){
                arr[i][j] = str.charAt(j)-'0'; // 문자->숫자 변환
            }
        }

        ArrayDeque<Node> deque = new ArrayDeque<>();

        // 초기화
        deque.add(new Node(0,0));
        dist[0][0] = 0;

        while(!deque.isEmpty()){
            Node node = deque.poll();
            int x = node.x;
            int y = node.y;
            for(int k=0; k<4; k++){
                int nx = x+dx[k];
                int ny = y+dy[k];
                if(nx>=0 && nx<n && ny>=0 && ny<m){
                    if(dist[nx][ny]==-1){
                        if(arr[nx][ny]==0){
                            dist[nx][ny] = dist[x][y];
                            deque.addFirst(new Node(nx,ny));
                        }else{
                            dist[nx][ny] = dist[x][y]+1;
                            deque.addLast(new Node(nx,ny));
                        }
                    }
                }
            }
        }

        System.out.println(dist[n-1][m-1]);

    }
}
class Node{
    int x,y;
    public Node(int x,int y){
        this.x = x;
        this.y = y;
    }
}

---

Python

큐 2개를 사용한 풀이

from collections import deque
dx = [0,0,1,-1]
dy = [1,-1,0,0]
m,n = map(int,input().split()) # m : 가로, n : 세로
a=[list(map(int,list(input()))) for _ in range(n)]
dist = [[-1]*m for _ in range(n)] # 해당 지점에 벽을 몇개 부수어야 갈수있는지를 저장. 


# ---- 초기값 ---- 
q = deque()
nxt_q = deque()
q.append((0,0))
dist[0][0] = 0

while q:
    x,y = q.popleft()
    for k in range(4):
        nx,ny = x+dx[k], y+dy[k]
        if 0 <= nx < n and 0 <= ny < m:
            if dist[nx][ny] == -1: # 방문을 안했을경우만
                if a[nx][ny] == 0: # 벽이 없는 곳으로 이동
                    dist[nx][ny] = dist[x][y]
                    q.append((nx,ny))
                else:    # 벽을 부숨.
                    dist[nx][ny] = dist[x][y] + 1
                    nxt_q.append((nx,ny))


    if not q: # 가장 적에 벽을 부수고 갈수있는 지점을 모두 방문
        q = nxt_q
        nxt_q = deque()


            
print(dist[n-1][m-1])