[BOJ 2206번] 벽 부수고 이동하기(JAVA)

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

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

class Node{
	int row, col, cnt, jump;
	Node(int row, int col, int cnt, int jump){
		super();
		this.row=row;
		this.col=col;
		this.cnt=cnt;
		this.jump=jump;
	}
}

class Main{
	
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	static int N, M, answer=Integer.MAX_VALUE;
	static int[][] map;
	static boolean[][][] isVisit;
	static int[] dx= {0, 0, -1, 1};
	static int[] dy= {-1, 1, 0, 0};
	
	public static void main(String args[]) throws Exception {
		String s[]=br.readLine().split(" ");
		N=Integer.parseInt(s[0]);
		M=Integer.parseInt(s[1]);
		map=new int[N][M];
		isVisit=new boolean[2][N][M];
		for(int i=0;i<N;i++) {
			String s1=br.readLine();
			for(int j=0;j<M;j++) {
				map[i][j]=s1.charAt(j)-'0';
			}
		}
		bfs();
		if(answer==Integer.MAX_VALUE) answer=-1;
		System.out.println(answer);
	}
	
	public static void bfs() {
		Queue<Node> q=new LinkedList<>();
		q.add(new Node(0, 0, 1, 0));
		
		while(!q.isEmpty()) {
			Node node=q.poll();
			int row=node.row;
			int col=node.col;
			int cnt=node.cnt;
			int jump=node.jump;
			
			if(row==N-1&&col==M-1) {
				answer=Math.min(answer, cnt);
				continue;
			}
			
			for(int i=0;i<4;i++) {
				int nextRow=row+dx[i];
				int nextCol=col+dy[i];
				if(nextRow>=0&&nextRow<N&&nextCol>=0&&nextCol<M) {
//					벽을 부슨 경우
					if(jump==1) {
						if(!isVisit[jump][nextRow][nextCol]&&map[nextRow][nextCol]==0) {
							isVisit[jump][nextRow][nextCol]=true;
							q.add(new Node(nextRow, nextCol, cnt+1, jump));
						}
					}
//					벽을 부수지 않은 경우
					else {
						if(map[nextRow][nextCol]==1) {
							if(!isVisit[jump+1][nextRow][nextCol]) {
								isVisit[jump+1][nextRow][nextCol]=true;
								q.add(new Node(nextRow, nextCol, cnt+1, jump+1));
							}
						}
						else if(map[nextRow][nextCol]==0) {
							if(!isVisit[jump][nextRow][nextCol]) {
								isVisit[jump][nextRow][nextCol]=true;
								q.add(new Node(nextRow, nextCol, cnt+1, jump));
							}
						}
					}
				}
			}
		}
		
	}
}

아래 블로그 링크를 참고하여 문제를 풀어보았습니다.

ghkvud2.tistory.com/14

[백준 2206번] 벽 부수고 이동하기_JAVA