백준 14442번 : 벽 부수고 이동하기2

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

14442번: 벽 부수고 이동하기 2

 

 

 

 

 

문제

• N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳, 1은 벽이 있는 곳을 나타낸다.
• (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 최단 경로로 이동하려 한다.
  • 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸
• 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.
• 첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

 

 

 

 

풀이

벽 부수고 이동하기 시리즈의 문제이다. 1에서는 벽을 한 개 까지 부수고 이동했지만, 이 문제에서는 K개까지 부수고 이동한다.

 

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

2206번: 벽 부수고 이동하기

 

 

 

그래서 벽 부수고 이동하기의 문제 풀이와 유사하다.

https://programmingiraffe.tistory.com/145

백준 - 2206번 : 벽부수고 이동하기

 

 

 

 

 

 상하좌우 인접한 칸으로 한 칸씩 이동했을 때의 최단 경로를 구하는 문제로, 한 칸씩 이동하며 사방탐색을 통해 모든 경우의 수에 대해 살피고 목표 지점에 도달했을시 탐색을 종료해야 한다. 따라서 큐를 이용한 BFS 알고리즘을 사용하여 문제를 풀었다.

 

 

 

1. 벽을 지금까지 몇 개 부쉈는지 정보 저장

 

 큐에 좌표 정보를 넣을 때, 행렬 좌표값, 이동 거리뿐만 아니라 지금까지 몇 개의 벽을 부순적이 있는지 정보를 저장할 필요가 있다. 따라서 좌표 정보를 담는 Point라는 객체에 int 형의 변수(hit)을 추가해줬다.

 

 

 

2. 방문체크 : boolean[K][N][M]

 

 방문체크를 할 때, 헤당 지점에 대해 지금까지 벽을 몇 번 부수고 방문했는가 안했는가를 표시했다. 해당 지점에 한번도 안부수고 방문할 수도 있고, 1번 부수고 방문할 수도 있고, .. K번 부수고 방문할 수도 있기 때문이다. 그리고 먼저 n번 부수고 방문했어도 후에 그 경로가 더이상 탐색이 불가능한 경로가 될 수도 있다.

 

 

* 백준의 문제 내 게시판에서 본건데, 배열의 차원 선언 순서가 메모리와 수행시간에 영향을 미친다고 한다. 

(https://www.acmicpc.net/board/view/111938)

 

visited[11][1000][1000]가 visited[1000][1000][11] 보다 메모리 사용량이 훨씬 적다. 채점을 돌렸을 때도 500ms 정도 차이가 났다.

 

 

 

3. 벽인지 벽이 아닌지에 따라 탐색을 다르게 했다.

 

• 벽이 아니다
  
  • 지금까지 n개 부숴 방문한적이 없음 => n개 그대로 탐색
• 벽이다
  • 지금까지 K개 미만 부숨
  • 지금까지 n +1개 부숴 방문한적이 없음=> n+1 부수고 탐색

 

 

 

 

 

코드

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

public class Main {
	static int N, M, K;
	static int[][] graph;
	static boolean[][][] visited;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	static class Point {
		int x;
		int y;
		int count;
		int hit;
		
		public Point(int x, int y, int count, int hit) {
			this.x = x;
			this.y = y;
			this.count = count;
			this.hit = hit;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		graph = new int[N + 1][M + 1];
		visited = new boolean[K + 1][N + 1][M + 1]; //0 : 벽 안부숨, 1~K: 벽 n개 부숨
		
		for(int i = 1; i <= N; i++) {
			String row = br.readLine();
			
			for(int j = 1; j <= M; j++) {
				graph[i][j] = row.charAt(j - 1) - '0';
			}
		}
		
		int answer = bfs(1, 1);
		
		System.out.println(answer);
	}
	
	public static int bfs(int i, int j) {
		Queue<Point> queue = new LinkedList<>();
		
		queue.add(new Point(i, j, 1, 0));
		visited[0][i][j] = true;
		
		while(!queue.isEmpty()) {
			Point point = queue.poll();
			
			if(point.x == N && point.y == M) { // 종료 조건
				return point.count;
			}
			
			for(int d = 0; d < 4; d++) {
				int nx = point.x + dx[d];
				int ny = point.y + dy[d];
				
				if(1 <= nx && nx <= N && 1 <= ny && ny <= M) {
					if(graph[nx][ny] == 0 && !visited[point.hit][nx][ny]) { //벽 아님
						queue.add(new Point(nx, ny, point.count + 1, point.hit));
						visited[point.hit][nx][ny] = true;
					}else if(graph[nx][ny] == 1 && point.hit < K && !visited[point.hit + 1][nx][ny]) { //벽 있음, k개 미만 부숨, n+1부수고 방문한적 없음
						queue.add(new Point(nx, ny, point.count + 1, point.hit + 1)); //벽 부수기
						visited[point.hit + 1][nx][ny] = true;
					}
				}
			}
		}
		
		return -1;
	}

}

 

 

 

 

 

결과

 

1480ms 걸리는 결과 : visited[11][1000][1000]

1992ms 걸리는 결과 : visited[1000][1000][11]

 

 

 

 

 

배운점

• 3차원 방문체크
  • visited[11][1000][1000] 가 visited[1000][1000][11] 보다 시간이 적게 든다