백준 2206번 : 벽 부수고 이동하기 (Java)

🔗 문제 링크

2206번: 벽 부수고 이동하기

---

📖 풀이 과정

 

- BFS 유형의 문제입니다.
- 특별한 조건 생각없이 하나씩 벽을 다 부숴보면서 해보려니 시간초과가 발생했습니다.(너무 문제를 안일하게 생각한 것 같습니다.) 
- 즉, BFS내에서 벽을 부수는 것에 대한 조건을 추가해야 합니다.
  - 그러므로, 내부 클래스 Point에 거리와 공사횟수에 대해 변수를 추가했습니다.
- 기존에 저는 visited 2차원 배열을 boolean 타입으로 선언하여 방문을 체크했지만 이번에는 공사횟수와 방문 여부를 동시에 체크했습니다.
  - visited 배열의 값은 모두 Integer.MAX_VALUE로 초기화합니다.
  - 이후, 공사 여부와 상관없이 visited배열의 값이 공사횟수보다 클 경우 그곳은 방문하지 않은 곳입니다.
  - 하지만, 방문한 곳은 공사 횟수 변수를 할당하여 비교를 합니다.
- 공사횟수는 한번만 가능하기에 공사횟수가 0일때만 queue에 추가적으로 Point 클래스 변수를 추가합니다.
- 이후 n,m위치에 다다른다면 변수를 반환합니다.

 

---

💻 코드

 

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 Main {
	static int n,m,result;
	static int[][] arr,visited;
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,-1,0,1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		arr = new int[n + 1][m + 1];
		visited = new int[n + 1][m + 1];
		
		for(int i = 1; i< n + 1; i++){
			String str = br.readLine();
			for(int j = 1; j< m + 1; j++){
				int value = Integer.parseInt(String.valueOf(str.charAt(j-1)));
				arr[i][j] = value;
				visited[i][j] = Integer.MAX_VALUE;
			}
		}
		result = getRoute(1,1);
		System.out.println(result);
	}
	
	private static int getRoute(int x, int y){
		Queue<Point> queue = new LinkedList<>();
		queue.offer(new Point(x, y,1,0));
		visited[x][y] = 0;
		
		while(!queue.isEmpty()){
			Point point = queue.poll();
			
			if(point.x == n && point.y == m){
				return point.count;
			}
			
			for(int i = 0; i< 4; i++) {
				int nowX = point.x + dx[i];
				int nowY = point.y + dy[i];
				
				if(nowX > 0 && nowY > 0 && nowX < n + 1 && nowY < m + 1){
					if(visited[nowX][nowY] > point.drill){
						if(arr[nowX][nowY] == 0){
							queue.offer(new Point(nowX,nowY,point.count + 1,point.drill));
							visited[nowX][nowY] = point.drill;
						}else{
							if(point.drill == 0){
								queue.offer(new Point(nowX,nowY,point.count + 1,point.drill + 1));
								visited[nowX][nowY] = point.drill + 1;
							}
						}
					}
				}
			}
		}
		return -1;
	}
	
	static class Point{
		int x, y,count, drill;
		
		public Point(int x, int y, int count, int drill) {
			this.x = x;
			this.y = y;
			this.count = count;
			this.drill = drill;
		}
	}
}