문제

BOJ 2206: 1261: 알고스팟 https://www.acmicpc.net/problem/1261

풀이

우선 최단 경로를 묻는 문제기 때문에 BFS를 사용하여 해결한다.

벽으로 막힌 경우 벽을 부수며 목적지까지 이동한다.

• BFS로 빈 공간일 때는 desCnt+0을, 벽을 부수고 다음 공간으로 넘어 갈 때는 desCnt+1을 하며 queue에 넣는다.
• desCnt(벽 부순 횟수를 세는 변수)가 적은 것을 먼저 꺼내며 탐색을 진행한다.
  • PriorityQueue를 이용해 desCnt가 더 적은 경우를 우선적으로 Queue에서 꺼내도록 한다.

코드

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

public class Main {
	
	static int N, M;
	static int[][] map;
	static boolean[][] isVisited;
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {1, -1, 0, 0};

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		isVisited = new boolean[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';
			}
		}
		
		int ans = bfs(0,0);
		
		System.out.println(ans);
	}
	
	static int bfs(int x, int y) {
		PriorityQueue<Pos> que = new PriorityQueue<>(); // 우선순위 큐를 사용하여 갈 수 있는 곳 먼저 모두 탐색하고 벽으로 막혀 있으면 벽을 부수고 탐색하도록 한다.
		int minDes = Integer.MAX_VALUE;
		
		que.add(new Pos(x, y, 0));
		isVisited[x][y] = true;
		
		while(!que.isEmpty()) {
			Pos p = que.poll();
			int curX = p.x;
			int curY = p.y;
			
			if(curX == N-1 && curY == M-1) { // 탈출 조건
				minDes = Math.min(minDes, p.desCnt);
				return minDes;
			}
			
			for(int t=0; t<4; t++) {
				int nx = curX + dx[t];
				int ny = curY + dy[t];
				
				if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
				
				if(!isVisited[nx][ny]) {
					if(map[nx][ny] == 0) { // 탐색한 좌표가 통과할 수 있는 길이면 큐에 넣는다.
						que.add(new Pos(nx, ny, p.desCnt));
					} 
					if(map[nx][ny] == 1) { // 탐색한 좌표가 벽이면 벽 부수는 횟수를 1 추가하여 큐에 넣는다.
						que.add(new Pos(nx, ny, p.desCnt + 1));
					}
					isVisited[nx][ny] = true;
				}
			}
			
		}
		return -1;
	}
	
	static class Pos implements Comparable<Pos>{ // 우선순위 큐를 사용할 것이기 때문에 Comparable을 구현한다.
		int x;
		int y;
		int desCnt;
		
		Pos(int x, int y, int desCnt){
			this.x = x;
			this.y = y;
			this.desCnt = desCnt;
		}
		
		@Override
		public int compareTo(Pos o) { // 인자로 전달한 o가 작다면 양의 정수를, 크다면 음의 정수를, 같다면 0을 반환한다.
			return this.desCnt - o.desCnt; // 벽 부순 횟수가 더 작은 경우를 우선으로 탐색하도록 한다.
		}
	}
	
}

정리

• PriorityQueue(우선순위 큐)를 사용하여 탐색에 우선순위 높은 경우를 먼저 탐색하는 법을 익혔다.
• PriorityQueue(우선순위 큐)를 사용하기 위해 Pos class에 Comparable의 compareTo 메소드를 구현하여 우선순위를 내가 정의하여 사용하는 법을 배웠다.