[백준] 1261 알고스팟 - JAVA

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

1261번: 알고스팟

 

 

[알고리즘]

• 벽을 최소한의 갯수로 부수고 목적지까지 다다르기 위해서 최소비용 BFS 알고리즘 적용 

---

 

[설계]

• (1,1) 지점부터 시작하여 이동
  1. 벽이 나올경우 : 벽 갯수+, 벽 부수기(0으로 변환) 후 이동 
  2. 빈 방이 나올경우 : 그냥 이동 
• 탐색 중 (N,M) 위치가 나올 경우, 벽 갯수 반환 
• Point 클래스 
  1. 현재 위치, 현재까지 부순 벽의 총 갯수 저장 
  2. Comparable 인터페이스를 구현하여 벽의 총 갯수 오름차순 정렬 
  3. 우선순위큐에 저장, 벽의 갯수가 적을수록 우선순위 ↑ 

---

 

[구현 과정]

• map[][] : 입력받은 미로 정보를 저장할 int 형 배열 
• Point 클래스 : (운영진이 이동중인 위치, 부순 벽의 총 갯수) 담고있는 클래스 , 벽의 갯수 적을수록 우선순위 높음 
• visited[][] : BFS 탐색 내에서 탐색 체크를 위한 boolean형 배열 

 

1. 입력받은 미로 크기와 정보를 map 배열에 저장 

 

2. BFS 탐색 시작 

 

3. Point 클래스를 저장하는 우선순위큐와, visited 배열을 생성한다. 출발지점을 큐에 add 하고 탐색체크한다. 

 

4. 큐가 빌 때까지 아래 과정을 반복한다. (bfs 구현) 

• 큐에서 하나 poll (=큐에 들어있는 Point 클래스 중 벽의 누적 갯수가 가장 작은 것) 
• poll한 위치가 만약 도착지라면, 누적된 벽의 갯수를 반환한다. (=우선순위큐에 의해 최소 갯수)
• 그렇지 않다면, 사방탐색으로 이동 
  1. 만약 이동한 위치가 미로를 벗어나거나 이미 탐색한 곳이라면 continue 
  2. 벽일 경우 : 벽 부수고, 방문체크 후 큐에 삽입 (벽 갯수 +1) 
  3. 빈 방일 경우 : 방문체크 후 큐에 삽입 

 

 

5. BFS 결과 출력 (= 도착지까지 누적된 벽의 최소 갯수)

 

---

 

[소스 코드]

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

public class Main {
	static int N, M;
	static int[][] map; 
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st;
		
		st= new StringTokenizer(br.readLine(), " ");
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		for(int i=0; i<N; i++) {
			String s= br.readLine();
			for(int j=0; j<M; j++) {
				map[i][j]= s.charAt(j)-'0'; 
			}
		}
		
		//bfs
		System.out.println(bfs()); 
		
	}//end of main
	
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,1};
	
	static boolean isOut(int x, int y) {
		return x<0 || x>= N || y<0 || y>=M; 
	}
	
	static class Point implements Comparable<Point>{
		int x;
		int y;
		int wall; //현재까지 부순 벽의 갯수 
		
		public Point(int x, int y, int wall){
			this.x= x;
			this.y= y;
			this.wall = wall; 
		}
		
		@Override
		public int compareTo(Point o) {
			return this.wall - o.wall; 
		}
	}
	static int bfs() {
		PriorityQueue<Point> que = new PriorityQueue<>(); 
		boolean visited[][] = new boolean[N][M]; 
		
		que.add(new Point(0,0,0));
		visited[0][0] = true;
		
		while(!que.isEmpty()) {
			Point p = que.poll();
			int x= p.x;
			int y= p.y;
			int wall = p.wall;
			
			//도착지일 경우
			if(x==N-1 && y==M-1) return wall; 
			
			for(int d=0; d<4; d++) {
				int nx= x+dx[d];
				int ny= y+dy[d];
				
				if(isOut(nx,ny) || visited[nx][ny]) continue;
				
				visited[nx][ny]=true;
				//벽일 경우 
				if(map[nx][ny]==1) {
					map[nx][ny]=0; //벽 부수고 
					que.add(new Point(nx, ny, wall+1)); 
				}
				
				//그냥 빈 곳 
				else que.add(new Point(nx,ny, wall)); 
			}
		}
		
		return -1; 
	}
}//end of class