[백준 - Java] 1261번 : 알고스팟

문제

www.acmicpc.net/problem/1261

1261번: 알고스팟

설명

처음엔 BFS로 최단 거리로 가면 되려나?라고도 생각했지만, 기존의 BFS로는 풀 수 없는 문제이다.

최단 거리도 필요 없고, (0, 0) 정점에서 부터 너비 우선 탐색을 해나가며 벽을 더 적게 부수는 방법으로 (M, N)까지 나아가야한다.

 

이를 위해서 기존의 Queue가 아니라 Deque를 사용했다.

Deque는 Queue의 앞 뒤로 값을 삽입할 수 있다.

Deque의 앞쪽을 더 우선순위가 높다고 가정하고, 뒤는 우선순위가 더 낮다고 가정한 뒤 Deque에 적절한 값을 삽입하는 것이다.

 

이를 문제에 적용해보면, 앞에서 언급했듯이 벽을 더 적게 부수는 방법으로 도착점까지 나아가야 한다고 했다.

이는 최대한 빈 방인 곳으로 이동하며, 벽을 부수지 않고는 나아갈 수 없는 그 이외의 경우에만 벽을 부숴야 한다.

 

BFS탐색을 하면서 빈방인 경우 addFirst()로 Deque의 앞에 삽입하고,

벽인 경우는 addLast()로 Deque의 뒤에 삽입하는 것이다.

 

그럼 BFS를 수행하며 Deque에서 값을 앞에서부터 하나씩 꺼내올 때 우선순위가 더 높은 빈방의 경우부터 나오게 될 것이다.

또한 벽을 부술 경우에는 벽을 부쉈다는 의미로 wall 변수를 +1씩 해주어 도착점에 도달했을 때 총 몇 개의 벽을 부쉈는지 알 수 있도록 한다.

이를 도착점을 만날 때까지 수행하면 끝이 난다.

(나는 클래스를 만들어 x값, y값, wall값을 가지도록 했다. 그리고 이 클래스를 자료형으로 갖는 Deque를 만들어 문제를 풀었다.

하지만 해당 좌표에 방문했는지 안 했는지를 체크하는 boolean 배열 visited를 int형으로 만들어 해당 배열에 바로 벽을 부순 값을 갱신해 나가며 문제를 풀어도 좋을 것 같다.)

전체 코드

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

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

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();

		map = new int[M][N];
		visited = new boolean[M][N];
		for(int i = 0; i < M; i++) {
			String str = sc.next();

			for(int j = 0; j < N; j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}

		bfs();

		System.out.println(ans);
	}

	public static void bfs() {
		// 일반 Queue가 아니라 Deque 사용 -> 삽입시 큐의 앞 뒤로 우선순위를 부여할 것 
		Deque<Point> queue = new ArrayDeque<>(); 
		queue.add(new Point(0, 0, 0));
		visited[0][0] = true;

		while(!queue.isEmpty()) {
			int cx = queue.peek().x;
			int cy = queue.peek().y;
			int cw = queue.pollFirst().wall; // 큐의 앞쪽부터 poll

			if(cx == M-1 && cy == N-1) {
				ans = cw;
				break;
			}

			for(int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];

				if(nx < 0 || ny < 0 || nx >= M || ny >= N || visited[nx][ny]) 
					continue;

				// 최소로 벽을 부술려면 최대한 빈 방을 위주로 가고, 그 이외에 벽을 부숴야 함 
				if(map[nx][ny] == 0) { // 빈 -> 우선순위가 더 높으니 큐의 앞에 삽입
					visited[nx][ny] = true;
					queue.addFirst(new Point(nx, ny, cw));
				} else if(map[nx][ny] == 1) { // 벽 -> 우선순위가 더 낮으니 큐의 뒤에 삽입
					map[nx][ny] = 0;
					visited[nx][ny] = true;
					queue.addLast(new Point(nx, ny, cw + 1)); // 벽 부쉈으니 cw+1 
				}
			}
		}
	}
	
}

class Point {
	int x;
	int y;
	int wall;

	Point(int x, int y, int wall) {
		this.x = x;
		this.y = y;
		this.wall = wall;
	}
}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%231261/src/Main.java

KwonMinha/BOJ