[백준/java] 6593번 : 상범 빌딩 - BFS

상범 빌딩

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

6593번: 상범 빌딩

이번 문제는 토마토와 비슷한 문제입니다.

 

https://drcode-devblog.tistory.com/269

[백준/java] 7569번 : 토마토(3차원배열) BFS

 

기존에 풀었었던 토마토 풀이에서, 불필요한 과정이 있었습니다.

 

map = new int[H][N][M];
visit = new boolean[H][N][M];
dx = new int[H][6];
dy = new int[H][6];
dh = new int[H][6];
		
for (int i = 0; i < H; i++) {
	dx[i][0] = 1; dx[i][1] = 0; dx[i][2] = -1; dx[i][3] = 0; dx[i][4] = 0; dx[i][5] = 0;
	dy[i][0] = 0; dy[i][1] = 1; dy[i][2] = 0; dy[i][3] = -1; dy[i][4] = 0; dy[i][5] = 0;
	dh[i][0] = 0; dh[i][1] = 0; dh[i][2] = 0; dh[i][3] = 0; dh[i][4] = 1; dh[i][5] = -1;
}

굳이 for문을 돌릴 필요가 없었으며, 

 

그냥 배열의 요소가 6개인 1차원 배열로 층, 행, 열 각각 만들어주면 되는 것이었습니다.

	static int[] dy = {1, 0, -1, 0, 0, 0};
	static int[] dx = {0, 1, 0, -1, 0, 0};
	static int[] dh = {0, 0, 0, 0, 1, -1};

 

기존에는 bfs() 함수 내에서 Queue 를 선언하여 풀었었는데,

 

이번에는 Queue를 클래스 내 전역변수로 활용하였습니다.

 

그 이유는 Queue에 "S"가 발견되는 위치를 즉각적으로 넣어서 풀 의도였습니다.

 

package dfsAndBfs;

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

public class P6539_SangBumBuilding {
	
	static char[][][] map;
	static boolean[][][] visit;
	static int l = 0, r = 0, c = 0, min = Integer.MAX_VALUE;
	static int[] dy = {1, 0, -1, 0, 0, 0};
	static int[] dx = {0, 1, 0, -1, 0, 0};
	static int[] dh = {0, 0, 0, 0, 1, -1};
	static Queue<Pos> q;
	static BufferedReader br;
	static BufferedWriter bw;
	
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		while(true) {
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			l = stoi(st.nextToken()); 
			r = stoi(st.nextToken()); 
			c = stoi(st.nextToken());
			
			if(l == 0 && r == 0 && c == 0) break;
			
			map = new char[l][r][c];
			visit = new boolean[l][r][c];
			q = new LinkedList<Pos>();
			min = 0;
			
			for (int i = 0; i < l; i++) {
				for (int j = 0; j < r; j++) {
					String str = br.readLine();
					
					for (int k = 0; k < c; k++) {
						map[i][j][k] = str.charAt(k);
						if(str.charAt(k) == 'S') {
							q.add(new Pos(i, j, k, 0));
							visit[i][j][k] = true;
						}
					}
					
				}
				
				br.readLine();
			}
			
			if(isFind()) bw.write("Escaped in " + min + " minute(s).\n");
			else bw.write("Trapped!\n");
		}
		
		bw.flush();
	}
	
	public static boolean isFind() {
		
		while(!q.isEmpty()) {
			Pos cur = q.poll();
			
			for (int i = 0; i < 6; i++) {
				int nh = dh[i] + cur.h;
				int ny = dy[i] + cur.y;
				int nx = dx[i] + cur.x;
				
				if(checkRange(ny, nx, nh) || visit[nh][ny][nx] || map[nh][ny][nx] == '#') continue;
				
				visit[nh][ny][nx] = true;
				int cnt = cur.cnt + 1;
				
				if(map[nh][ny][nx] == 'E') {
					min = cnt;
					return true;
				}
				
				q.add(new Pos(nh, ny, nx, cnt));
			}
		}
		
		return false;
	}
	
	public static boolean checkRange(int y, int x, int h) {
		return y < 0 || y >= r || x < 0 || x >= c || h < 0 || h >= l;
	}
	
	public static int stoi(String str) {
		return Integer.parseInt(str);
	}
	
	static class Pos {
		int y, x, h, cnt;
		
		public Pos(int h, int y, int x, int cnt) {
			this.h = h;
			this.y = y;
			this.x = x;
			this.cnt = cnt;
		}
	}
}