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

 

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

 

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

2206번: 벽 부수고 이동하기

2206번 벽 부수고 이동하기.java

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

 

2206번 벽 부수고 이동하기 

문제

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

설명

bfs를 통해 풀 수 있다.

 

일반적인 bfs와 가장 큰 차이는 벽을 부순다는 점이다. 이동 시마다 현재 내가 벽을 부순 상태인지 아닌지를 구분해야 한다. 따라서 visit 배열을 3차원으로 만들어서 벽을 부수고 이동한 상태인지 벽을 안 부수고 이동한 상태인지를 구분한다.

 

벽을 부수지 않은 상태라면 벽인 곳으로도 이동할 수 있다. 

 

벽을 부순 상태라면 길로만 이동할 수 있다.

 

위와 같은 경우의 수를 구분지어 bfs를 사용하면 된다.

코드

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

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

public class 벽_부수고_이동하기_2206 {
	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[][] map = new int[N+1][M+1];
		int[][][] visit = new int[N+1][M+1][2];
		
		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);
		int answer = Integer.MAX_VALUE;
		for(int i=0;i<2;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[] 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<1 && 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));
        			}
    			}
    		}
    	}
    }
}