[백준BOJ] 14442번 벽 부수고 이동하기2.java

 

백준 저지에서 벽 부수고 이동하기2를 자바를 통해 풀어 보았다. 

 

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

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

14442번 벽 부수고 이동하기2.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

14442번 벽 부수고 이동하기2 

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

설명

벽 부수고 이동하기에 이어지는 문제이다.

 

달라진 것은 부술 수 있는 벽의 개수이다. 벽 부수고 이동하기 문제에서 1개만 부술 수 있던 벽을 K로 바꿔주면 바로 풀 수 있다.

코드

//14442번 벽 부수고 이동하기2.java
package boj20211215;

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

public class 벽_부수고_이동하기2_14442 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    static class position{
    	int i;
    	int j;
    	int wall;
    	position(int i, int j, int wall) {
			this.i=i;
			this.j=j;
			this.wall=wall;
		}
    }
    public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int[][] map = new int[N+1][M+1];
		int[][][] visit = new int[N+1][M+1][K+1];
		
		for(int i=1;i<=N;i++) {
			String line = br.readLine();
			for(int j=1;j<=M;j++) {
				map[i][j] = Integer.parseInt(line.substring(j-1,j));
			}
		}
		
		bfs(map, visit, new position(1, 1, 0),N,M,K);
		int answer = Integer.MAX_VALUE;
		for(int i=0;i<=K;i++) {
			if(visit[N][M][i]!=0 && answer > visit[N][M][i]) {
				answer = visit[N][M][i];
			}
		}
		if(answer==Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(answer);
	}
    
    static void bfs(int[][]map, int[][][] visit, position start, int N, int M, int K) {
    	int[] di = {1,-1,0,0};
    	int[] dj = {0,0,1,-1};
    	Queue<position> q = new LinkedList<position>();
    	q.add(start);
    	visit[start.i][start.j][start.wall]=1;
    	while(!q.isEmpty()) {
    		position now = q.poll();
    		for(int d=0;d<4;d++) {
    			int i = now.i+di[d];
    			int j = now.j+dj[d];
    			int w = now.wall;
    			
    			if(1<=i && i<=N && 1<=j && j<=M) {
    				if(map[i][j]==0 && visit[i][j][w]==0) {
        				//벽이 아닌 경우
        				visit[i][j][w] = visit[now.i][now.j][now.wall]+1;
        				q.add(new position(i, j, w));
        			}
    				
        			if(map[i][j]==1 && w<K && visit[i][j][w+1]==0) {
        				//벽이지만 부술 수 있는 경우
        				visit[i][j][w+1] = visit[now.i][now.j][now.wall]+1;
        				q.add(new position(i, j, w+1));
        			}
    			}
    		}
    	}
    }
}