[Baekjoon] 14442_벽 부수고 이동하기 2

문제(출처: https://www.acmicpc.net/problem/14442)

---

< 벽 부수고 이동하기 2 >

 

문제 풀이 

 

현재 위치에서 상하좌우로 이동하면서 벽이 없다면 이동, 벽이 있다면 현재까지 부순 벽 개수를 보고 부수고 이동한다.

 

my solution (Java)

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 _14442_ { // 벽 부수고 이동하기 2
	static int arr[][], n, m, k;
	static boolean visited[][][];

	static class Pair {
		int x, y, d, w;

		public Pair(int x, int y, int d, int w) {
			this.x = x;
			this.y = y;
			this.d = d;
			this.w = w;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());

		arr = new int[n][m];
		visited = new boolean[k + 1][n][m];

		for (int i = 0; i < n; i++) {
			String str = bf.readLine();
			for (int j = 0; j < m; j++) {
				arr[i][j] = str.charAt(j) - '0';
			}
		}

		if (n == 1 && m == 1) {
			System.out.println(1);
		} else {
			System.out.println(bfs());
		}

	}

	private static int bfs() {
		Queue<Pair> queue = new LinkedList<>();
		queue.add(new Pair(0, 0, 1, 0));
		visited[0][0][0] = true;

		int dx[] = { -1, 1, 0, 0 };
		int dy[] = { 0, 0, -1, 1 };

		while (!queue.isEmpty()) {
			Pair pair = queue.poll();
			for (int i = 0; i < 4; i++) {
				int x = pair.x + dx[i];
				int y = pair.y + dy[i];
				if (x >= 0 && x < n && y >= 0 && y < m) {
					if (arr[x][y] == 0 && !visited[pair.w][x][y]) {
						if (x == n - 1 && y == m - 1) {
							return pair.d + 1;
						}
						visited[pair.w][x][y] = true;
						queue.add(new Pair(x, y, pair.d + 1, pair.w));
					} else if (arr[x][y] == 1 && pair.w + 1 <= k && !visited[pair.w + 1][x][y]) {
						if (x == n - 1 && y == m - 1) {
							return pair.d + 1;
						}
						visited[pair.w + 1][x][y] = true;
						queue.add(new Pair(x, y, pair.d + 1, pair.w + 1));
					}
				}
			}
		}
		return -1;
	}
}

변수)
n, m, k : 맵 크기, 부술 수 있는 벽의 수
arr : 맵
visited : 방문 여부  

 

Pair

현재 위치와 이동 거리, 부순 벽의 개수를 관리한다.

 

Main

맵 크기 n, m과 부술 수 있는 벽의 수인 k를 입력받는다. 맵 정보를 입력받아 arr에 저장한다. 만약 n과 m 값이 1이라면 최단 경로는 1이므로 1을 출력하고, 그렇지 않다면 bfs() 함수의 반환값을 출력한다.

 

bfs()

큐에 시작위치 (0,0)과 이동거리 1, 부순 벽의 개수 0을 가진 Pair 객체를 저장한다. 부순 벽의 개수 0과 현재 위치 (0,0)을 방문처리한다. 큐가 빌 때까지 다음 과정을 반복한다.

 

상하좌우 탐색 후 맵 범위 안이라면

1) 이동할 수 있는 곳이고 아직 방문하지 않은 곳이라면 -> 방문처리 및 큐에 저장 

2) 벽이고 아직 k개의 벽을 안 부쉈고 아직 방문하지 않은 곳이라면 -> 방문 처리 및 큐에 저장

이때, 둘 다 (n-1, m-1) 위치에 도착했다면 현재 이동 거리 +1을 반환한다.

 

(n-1, m-1)에 도착하지 못한다면 -1을 반환한다.

---

---