[백준: Java] 14442 - 벽 부수고 이동하기 2

[문제]

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

조건에 따라 최단 경로가 달리지는 문제입니다. 벽 부수고 이동하기와의 차이점은 벽을 부수는 횟수 차이입니다.

 

최근에 봤던 기업의 코딩테스트에서 유사한 유형의 문제가 출제되었습니다.

 

조건에 따라 다르게 이동하는 테크닉을 익혀두는 것도 좋을 거 같습니다.

 

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

위 문제도 해당 문제와 풀이 방식이 유사합니다.

---

[초기화]

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n, m, k;
	static char[][] map;
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		map = new char[n][m];
		
		for(int i = 0; i < n; i++) {
			String line = br.readLine();
			for(int j = 0; j < m; j++)
				map[i][j] = line.charAt(j);
		}
		
		solve();
	}

	static class Node {
		int step, y, x, cnt;

		public Node(int step, int y, int x, int cnt) {
			this.step = step;
			this.y = y;
			this.x = x;
			this.cnt = cnt;
		}
	}

현재 걸음과 위치, 벽을 뚫을 수 있는 횟수를 저장하는 노드 클래스를 선언합니다.

---

[풀이]

		int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
		boolean[][][] visited = new boolean[k + 1][n][m];
		ArrayDeque<Node> q = new ArrayDeque<>();
		q.add(new Node(1, 0, 0, k));
		visited[k][0][0] = true;
		
		while(!q.isEmpty()) {
			Node current = q.poll();
			if(current.y == n - 1 && current.x == m - 1) {
				System.out.println(current.step);
				return;
			}
			
			for(int[] d: directions) {
				int my = current.y + d[0];
				int mx = current.x + d[1];
				
				if(0 <= my && my < n && 0 <= mx && mx < m) {
					if(map[my][mx] == '1' && current.cnt > 0 && !visited[current.cnt - 1][my][mx]) {  // 벽을 부술 수 있는 경우
						visited[current.cnt - 1][my][mx] = true;
						q.add(new Node(current.step + 1, my, mx, current.cnt - 1));
					} if(map[my][mx] == '0' && !visited[current.cnt][my][mx]) {  // 벽을 안 부숴도 되는 경우
						visited[current.cnt][my][mx] = true;
						q.add(new Node(current.step + 1, my, mx, current.cnt));
					}
				}
			}
		}
		System.out.println(-1);
	}

상화좌우로 이동이 가능하므로, 이를 나타낼 방향벡터를 정의합니다.

 

방문 여부를 체크할 배열도 정의합니다.

이때 벽을 부술 수 있는 횟수에 따라 이동할 수 있는 위치가 달라지므로, 현재 상황에 맞는 방문 여부를 확인할 수 있도록 3차원 배열로 정의합니다.

 

벽을 부순다고 최단 경로를 보장할 수 없고, 벽을 부수지 않는다고 최단 경로를 보장할 수 없습니다. 즉 어느 상황일 때 최단 경로가 되는지 모르기 때문에 상태에 따라 관리하도록 3차원 배열을 이용합니다.

 

기본적인 준비가 완료됐다면 BFS를 통해 최단 경로를 탐색합니다.

1. 현재 노드 확인
   1. 현재 노드가 목적지에 도달했다면 이동한 거리 출력 후, 종료
2. 네 방향에 맞춰 탐색
   1. 이동하려는 범위가 유효하다면
      1. 해당 지점을 아직 방문하지 않았고, 벽을 부술 수 있는 경우 다음 탐색을 위해 큐에 저장
      2. 해당 지점을 아직 방문하지 않았고, 벽을 안 부숴도 되는 경우 다음 탐색을 위해 큐에 저장
3. 모든 탐색이 끝났음에도 목적지에 도달하지 못했다면 -1 출력

---

[전체 코드]

package 백준.골드;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class BOJ_14442_벽부수고이동하기2 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n, m, k;
	static char[][] map;
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		map = new char[n][m];
		
		for(int i = 0; i < n; i++) {
			String line = br.readLine();
			for(int j = 0; j < m; j++)
				map[i][j] = line.charAt(j);
		}
		
		solve();
	}
	
	static void solve() {
		int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
		boolean[][][] visited = new boolean[k + 1][n][m];
		ArrayDeque<Node> q = new ArrayDeque<>();
		q.add(new Node(1, 0, 0, k));
		visited[k][0][0] = true;
		
		while(!q.isEmpty()) {
			Node current = q.poll();
			if(current.y == n - 1 && current.x == m - 1) {
				System.out.println(current.step);
				return;
			}
			
			for(int[] d: directions) {
				int my = current.y + d[0];
				int mx = current.x + d[1];
				
				if(0 <= my && my < n && 0 <= mx && mx < m) {
					if(map[my][mx] == '1' && current.cnt > 0 && !visited[current.cnt - 1][my][mx]) {  // 벽을 부술 수 있는 경우
						visited[current.cnt - 1][my][mx] = true;
						q.add(new Node(current.step + 1, my, mx, current.cnt - 1));
					} if(map[my][mx] == '0' && !visited[current.cnt][my][mx]) {  // 벽을 안 부숴도 되는 경우
						visited[current.cnt][my][mx] = true;
						q.add(new Node(current.step + 1, my, mx, current.cnt));
					}
				}
			}
		}
		System.out.println(-1);
	}
	
	static class Node {
		int step, y, x, cnt;

		public Node(int step, int y, int x, int cnt) {
			this.step = step;
			this.y = y;
			this.x = x;
			this.cnt = cnt;
		}
	}
}

---