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

 문제

www.acmicpc.net/problem/14442

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

14442 벽 부수고 이동하기 2

 

 구현 방법

 벽을 한 개까지 부수고 이동할 수 있기 때문에 방문을 관리하는 visited 배열을 3차원으로 선언하여 좌표와 벽을 부술 수 있는지에 대한 여부를 관리해줍니다. 상하좌우를 검사하여 빈 칸이 일 때에는 그냥 지나가고 벽일 때 현재 좌표에서 벽을 부술 수 있다면 벽을 부수고 지나가줍니다. 이동을 하다가 (N, M) 좌표까지 가게 된다면 반복문을 끝내주고 거리를 리턴, 반복문이 그대로 끝난다면 불가능하므로 -1을 출력해줍니다.

 

 구현 코드

package BOJ.Gold;

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 BOJ14442_벽부수고이동하기2 {
	static int R, C, K, cnt;
	static boolean[][][] visited;
	static int[][] map, deltas= {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static Queue<Move> queue;
	static class Move {
		int r, c, wallB;

		public Move(int r, int c, int wallB) {
			super();
			this.r = r;
			this.c = c;
			this.wallB = wallB;
		}	
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		map = new int[R][C];
		visited = new boolean[R][C][K+1];
		for (int r=0;r<R;r++) {
			String input = br.readLine();
			for (int c=0;c<C;c++) {
				map[r][c] = input.charAt(c)-'0';
			}
		}
		// 입력완료
		queue = new LinkedList<>();
		queue.offer(new Move(0, 0, 0));
		visited[0][0][0] = true;
		cnt = 1;
		boolean flag = bfs();
		if (flag) System.out.println(cnt);
		else System.out.println(-1);
	}
	
	static boolean bfs() {
		while(!queue.isEmpty()) {
			int size = queue.size();
			for (int i=0;i<size;i++) {
				Move now = queue.poll();
				if (now.r==R-1 && now.c==C-1) return true;
				for (int d=0;d<4;d++) {
					int nr = now.r+deltas[d][0];
					int nc = now.c+deltas[d][1];
					if (isIn(nr, nc)) {
						if (map[nr][nc]==0 && !visited[nr][nc][now.wallB]) {
							visited[nr][nc][now.wallB] = true;
							queue.offer(new Move(nr, nc, now.wallB));
						} else if (map[nr][nc]==1 && now.wallB<K && !visited[nr][nc][now.wallB+1]) {
							visited[nr][nc][now.wallB+1] = true;
							queue.offer(new Move(nr, nc, now.wallB+1));
						}
					}
				}
			}
			cnt++;
		}
		
		return false;
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!