[BOJ] 16933. 벽 부수고 이동하기3 - JAVA

🔗 문제

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

16933번: 벽 부수고 이동하기 3

 

🧩 풀이 및 코드

문제 유형 : 그래프 이론, 그래프 탐색, 너비우선탐색(BFS)

 

풀이

참고 - https://wngml56.tistory.com/80

[BOJ] 14442. 벽 부수고 이동하기2 - JAVA

 

 

느낀 점

처음으로 혼자 로직 오류를 찾아 해결했다. 예전엔 예제에 나와있는 테케가 다 맞았는데 틀렸다가 뜨면 히든 테케가 무엇인지 어디가 잘못된 건지 찾지 못하고 다른 사람 코드를 봤다. 이번엔 혼자 찾아 해결할 수 있었다. 점점 성장하고 있는 것 같아 좋다. 예전과의 차이는 다양한 문제를 풀어본 경험과 알고리즘 로직을 대충 이해한 것과 정확히 이해한 것의 차이인 것 같다. 벽부수고이동하기 감을 잃지 않기 위해 내일 마지막 남은 벽부수고이동하기4 를 풀어봐야 겠다. 

 

전체 코드

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

public class Main_bj_16933_벽부수고이동하기3 {
	
	static int N, M, K;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_16933.txt"));
		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());
		
		int[][][] map = new int[N][M][K+1];		// 0은 벽을 깨지 않은 경우, k는 k번 깬 경우
		for(int i=0; i<N; i++) {
			String s = br.readLine();
			for(int j=0; j<M; j++) {
				map[i][j][0] = s.charAt(j) -'0';
				
				if(map[i][j][0] == 1) {
					for(int k=0; k<=K; k++) {
						map[i][j][k] = -1;
					}
				}
			}
		}
		
		System.out.println(BFS(map));
		br.close();
	}
	
	static class Loc {
		int x;
		int y;
		int wall;
		
		Loc(int x, int y, int wall) {
			this.x = x;
			this.y = y;
			this.wall = wall;
		}
	}
	
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int BFS(int[][][] map) {
		Queue<Loc> que = new ArrayDeque<>();
		map[0][0][0] = 1;
		que.add(new Loc(0, 0, 0));
		
		boolean day = true;
		int res = Integer.MAX_VALUE;
		int size = que.size();
		while(!que.isEmpty()) {
			Loc now = que.poll();
			
			if(now.x == N-1 && now.y == M-1) {
				res = Math.min(res, map[now.x][now.y][now.wall]);
			}
			
			if(size-- == 0) {
				day = !day;
				size = que.size();
			}
			
			boolean wait = false;
			for(int d=0; d<4; d++ ) {
				int nx = now.x + dx[d];
				int ny = now.y + dy[d];
				
				if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
				if(map[nx][ny][now.wall] == 0) {
					map[nx][ny][now.wall] = map[now.x][now.y][now.wall] + 1;
					que.add(new Loc(nx, ny, now.wall));
				}
				if(day && now.wall+1 <= K && map[nx][ny][now.wall+1] == -1) {
					map[nx][ny][now.wall+1] = map[now.x][now.y][now.wall] + 1;
					que.add(new Loc(nx, ny, now.wall+1));
				}
				if(!day && now.wall+1 <= K && map[nx][ny][now.wall+1] == -1) {	// 밤이어서 막혔다면
					wait = true;
				}
			}
			
			if(wait) {		// 밤이여서 막혔다면 기다리기
				map[now.x][now.y][now.wall]++;
				que.add(now);
			}
		}
		
		if(res>=Integer.MAX_VALUE) return -1;
		else return res;
	}
	
}