[백준] G3 14442 벽 부수고 이동하기 2 (java)

www.acmicpc.net/problem/14442

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

 

풀이

 

1) 입력값을 저장할 map[][]과 방문체크용 배열 isVisited[][][]를 생성한다.

2) bfs를 돌리기위해 필요한 함수, 변수를 클래스를 생성한다. 클래스의 멤버는 좌표(r,c), 벽뚫은 횟수 (k), 이동 횟수(t).

3) (0,0) 에서 bfs를 돌린다

• (N-1,M-1)에 도착하면 이동 횟수(t) +1 을 출력 후 리턴
• 벽을 부술 수 없는 경우 : k
• 벽을 부술 수 있는 경우 : k+1

4) while문이 끝나도 return이 안되었을 경우 불가능한 경우이다. -> -1 출력 후 리턴

 

주의사항

 

1) k+1이 K보다 커지면 안됨

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G3_14442_벽부수고이동하기2 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,M,K,map[][];
	static boolean isVisited[][][];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		K = Integer.parseInt(tokens.nextToken());
		map = new int[N][M];
		isVisited = new boolean[N][M][K+1];
		for(int r=0; r<N; r++) {
			String line = input.readLine();
			for(int c=0; c<M; c++) {
				map[r][c] = line.charAt(c) - '0';
			}	
		}
		bfs();
	}

	private static void bfs() {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(0, 0, 0, 0));
		isVisited[0][0][0] = true;
		
		while(!queue.isEmpty()) {
			Node front = queue.poll();
			
			if(front.r == N-1 && front.c == M-1) {
				System.out.println(front.t+1);
				return;
			}
			
			for(int d=0; d<4; d++) {
				int nr = front.r + dr[d];
				int nc = front.c + dc[d];
				int nk = front.k;
				int nt = front.t + 1;
				if(isIn(nr, nc) && !isVisited[nr][nc][nk]&& map[nr][nc] == 0) {
					isVisited[nr][nc][nk] = true;
					queue.offer(new Node(nr, nc, nk, nt));
				}
				if(front.k != K) {
					nk = Math.min(front.k+1, K);
					
					if(isIn(nr, nc) && !isVisited[nr][nc][nk] && map[nr][nc] == 1) {
						isVisited[nr][nc][nk] = true;
						queue.offer(new Node(nr, nc, nk, nt));
					}
				}
			}
		}
		System.out.println(-1);
		return;
		
	}
	static class Node{
		int r;
		int c;
		int k;
		int t;
		public Node(int r, int c, int k, int t) {
			super();
			this.r = r;
			this.c = c;
			this.k = k;
			this.t = t;
		}
		@Override
		public String toString() {
			return "Node [r=" + r + ", c=" + c + ", k=" + k + ", t=" + t + "]";
		}
	}
	
	static int dr[] = {0,0,-1,1};
	static int dc[] = {-1,1,0,0};
	
	static boolean isIn(int r, int c) {
		return (r>=0 && c>=0 && r<N && c<M);
	}
	static String src =
			"6 4 1\r\n" + 
			"0100\r\n" + 
			"1110\r\n" + 
			"1000\r\n" + 
			"0000\r\n" + 
			"0111\r\n" + 
			"0000";
}

 

 

후기

 

 장담컨데 며칠전 "말이 되고픈 원숭이"와 "움직이는 미로 탈출"을 안풀었다면 절대로 못풀었을 것이다.

2번 당하고 나니 보자마자 중간에 끊어야하는 제약조건이 있네? 3차원 배열이구나! 하고 바로 풀 수 있었다.

역시 경험이 중요하다.