백준 14442번 - 벽 부수고 이동하기2

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

14442번: 벽 부수고 이동하기 2

이번문제는 의 응용버전으로 이번에는 벽을 주어진 횟수만큼 부수고 이동할 경우에 미로탐색을 하여

최단거리를 구해주는 문제이다. 이번 문제도 기본적으로는 BFS(Breadth-First Search) 를 사용하여 해결할 수 있다.

 

이번에는 미로탐색1 문제에서의 로직을 사용해도 되지만 조금 변형해서 사용해보자.

 

1. 미로의 map (행렬)을 만들어 탐색을 수행준비.

 

2. 미로와 같은 행렬의 크기인 새로운 행렬 visit(방문확인 행렬) 을 생성한다. visit[x][y][z] 라고 했을 경우

x는 row 의 위치 y는 col 의 위치 z는 몇번째 벽을 부쉈는지의 index 로 mapping 시켜준다.

해당 3차 배열은 boolean 형으로 생성해준다.

 

3. Node class 를 생성하여 해당 노드에 행,열 위치정보와 현재 몇칸을 건너왔는지에 대한정보 그리고 몇개의 벽을 쉈는지에 대한 정보를 넣어준다.

 

4. 해당 Node 객체를 가지고 Queue 를 생성하여 Enqueue, Dequeue 를 반복하여 Queue 에 Node 객체가 사라질 때까지 너비탐색을 진행하여 미로를 탐색해준다.

 

5. Enqueue Dequeue 작업에서는 너비탐색으로 다음위치로 향할 경우에 해당 위치가 벽인지 아닌지 체크하고 방문배열도 체크해준다.

 

6. Queue 에 모든 객체요소가 사라지거나 Queue 에 존재하는 Node 객체의 row,col 정보가 맨 마지막 row,col 인 경우에멈춰주고 답을 도출한다.

 

 

예시를 들기위해서 아래와 같은 미로가 존재한다고 해보자.

첫번째 칸을 방문하였으므로 방문배열에는 아래와 같이 표시해주면 된다 표시가 안되어있는 칸은 모두 false 라고 생각하면 된다. 빨간점으로 표시된 부분은 true 값이라고 생각하면 된다.

 

그 다음으로 방향을 아래쪽으로 향한다고 해보자.

그럼 아래와 같은 map 의 결과가 나올것이다.

해당 결과에 대한 방문배열은 아래와 같이 표시할 수 있다.

위와같은 논리로 코딩을해주면 아래와 같다.

 

1. JAVA

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

public class Main {
	
	static int N,M,C;
	static boolean[][][] visit;
	static int[][] map;
	static int[] dr = {1,-1,0,0};
	static int[] dc = {0,0,-1,1};
	
	static class Nods {
		int r,c,step,crash;
		
		public Nods(int r, int c, int step, int crash) {
			this.r = r;
			this.c = c;
			this.step = step;
			this.crash = crash;
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] rowCol = br.readLine().split(" ");
		N = Integer.parseInt(rowCol[0]);
		M = Integer.parseInt(rowCol[1]);
		C =  Integer.parseInt(rowCol[2]);
		
		map = new int[N][M];
		visit = new boolean[N][M][11];
		
		for (int i = 0; i < N; i++) {
			String[] inputs = br.readLine().split("");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(inputs[j]);
			}
		}//for
		
		int result = bfs();
		
		bw.write(result + "");
		bw.close();
		br.close();
		
	}
	
	static int bfs() {
		Queue<Nods> queue = new ArrayDeque<>(); 
		queue.add(new Nods(0,0,1,0));
		visit[0][0][0] = true;
		
		while(!queue.isEmpty()) {
			Nods nd = queue.poll();
			
			if (nd.r == N-1 && nd.c == M-1) return nd.step;
			
			for (int i = 0; i < 4; i++) {
				int nr = nd.r + dr[i];
				int nc = nd.c + dc[i];
				
				if (nr <0 || nc <0 || nr >= N || nc >= M) continue;
				
				if (map[nr][nc] == 0 && !visit[nr][nc][nd.crash]) {
					queue.offer(new Nods(nr,nc,nd.step+1,nd.crash));
					visit[nr][nc][nd.crash] = true;
				}
				
				if (map[nr][nc] == 1 && nd.crash < C && !visit[nr][nc][nd.crash+1]) {
					queue.offer(new Nods(nr,nc,nd.step+1,nd.crash+1));
					visit[nr][nc][nd.crash+1] = true;
				}
				
			}//for
		}//while
		return -1;
	}
	
}

 

 

2.C++

#include <iostream>
#include <queue>

using namespace std;

int N,M,R;
int map[1001][1001];
bool visit[1001][1001][11];
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};

int bfs();

typedef struct {
    int r,c,step,crash;
} nods;

int main() 
{
    scanf("%d %d %d",&N,&M,&R);

    char line[M+1];

    for (int i = 0; i < N; i++) {
        scanf("%s",line);
        for (int j = 0; j < M; j++) {
            map[i][j] = line[j] - '0';
        }
    }

    printf("%d",bfs());

    return 0;
}

int bfs() {
    queue<nods> q;
    nods ns = {0,0,1,0};
    q.push(ns);

    while(!q.empty()) {
        nods nd = q.front();
        q.pop();

        if (nd.r == N-1 && nd.c == M-1) return nd.step;

        for (int i = 0; i < 4; i++) {
            int nr = nd.r + dr[i];
            int nc = nd.c + dc[i];

            if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;

            if (map[nr][nc] == 0 && !visit[nr][nc][nd.crash]) {
                nods n = {nr,nc,nd.step+1,nd.crash};
                q.push(n);
                visit[nr][nc][nd.crash] = true;
            }

            if (map[nr][nc] == 1 && nd.crash < R && !visit[nr][nc][nd.crash+1]) {
                nods n = {nr,nc,nd.step+1,nd.crash+1};
                q.push(n);
                visit[nr][nc][nd.crash + 1] = true;
            }
        }
    }
    return -1;
}