[백준 2206] 벽 부수고 이동하기 (JAVA)

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

2206번: 벽 부수고 이동하기

 

DFS로 풀었다가 시간 초과가 발생해서 BFS로 다시 풀이한 문제였다!

BFS는 덜 익숙하다는게 너무나도 느껴졌다...

 

1)객체를 만들어서 x,y,벽 사용여부, 현재까지의 거리값 을 속성값으로 갖는다.

2) int형의 2차원 배열 check로 벽 사용여부를 넣는다. 이때, 벽 사용여부를 넣는 이유는!

만일 x,y가 벽이 아닌 곳인데 벽을 사용한 상태로 이미 통과된 적이 있다면,

벽을 사용하지 않은 경로로 x,y에 도달했을때는 x,y를 통과할 수 있도록 하기 위해서이다!

 

 아래의 코드를 확인해주시길 바랍니다!

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

public class Main {
	static int n, m;
	static int[][] arr, dp;
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };
	static int[][] check;
	static class Mode{
		int x;
		int y;
		int chance;
		int value;
		Mode(int x,int y, int chance,int value){
			this.x =x;
			this.y=y;
			this.chance=chance;
			this.value= value;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		arr = new int[n + 1][m + 1];
		dp = new int[n + 1][m + 1];
		check = new int[n + 1][m + 1];
		for (int i = 1; i <= n; i++) {
			String[] strArr = br.readLine().split("");
			for (int j = 1; j <= m; j++) {
				arr[i][j] = Integer.parseInt(strArr[j - 1]);
				check[i][j]=Integer.MAX_VALUE;
			}

		}

		bw.write(Integer.toString(find(1, 1, 0, 1)));
		bw.flush();
		bw.close();
		br.close();
	}

	static int find(int x, int y, int chance, int value) {
		Queue<Mode> q = new LinkedList<>();
		q.add(new Mode(x,y,chance,value));
		while(!q.isEmpty()) {
			Mode m1 = q.poll();
			int chanceTemp=m1.chance;
			int mx=m1.x;
			int my=m1.y;
			int mvalue=m1.value;
			if(mx==n&&my==m) {
				return mvalue;
			}
			for (int i = 0; i < 4; i++) {
				int xx = mx + dx[i];
				int yy = my + dy[i];
				if (xx > 0 && yy > 0 && xx <= n && yy <= m)
					if (check[xx][yy]>chanceTemp) {
						if(arr[xx][yy]==0) {
							check[xx][yy] = chanceTemp;
							q.add(new Mode(xx, yy, chanceTemp, mvalue+1));
						}
						else if(arr[xx][yy]==1&&chanceTemp==0) {
							check[xx][yy] = chanceTemp+1;
							q.add(new Mode(xx, yy,1, mvalue+1));
						}
					}
			}
		}
		return -1;
	}

}