문제

토마토

풀이

이 문젠 솔직히 bfs의 전형적인 문제라 알고리즘을 틀렸다기 보다는 3차원 배열을 정의하는데 있어서 시간을 좀 더 많이 들였던것 같습니다.
저는 개인적으로 3차원 배열을 다를 수 있는 기회가 실제 프로젝트에서 있지는 않아서.. 아마 게임개발쪽이시면 그냥 푸실거같으네요.

BFS하면 큐겠죠. 큐를 정의하는데 저는 배열로 넣고 빼겠습니다.

Queue<int[]> q = new LinkedList<>();
// 높이
for (int i = 0; i < h; i++) {
	// 세로
	for (int j = 0; j < n; j++) {
		st = new StringTokenizer(br.readLine());
        // 가로
		for (int k = 0; k < m; k++) {
			box[i][j][k] = Integer.parseInt(st.nextToken());
			if (box[i][j][k] == 1) {
				q.add(new int[] {i, j, k});
			}
		}
	}
}

높이(h) 세로(y) 가로(x) 순으로 for문을 돌리고 높이, 세로, 가로 순으로 큐에 넣습니다. 큐에 넣는 이유는 1인 것부터 차례대로 BFS 큐에넣고 0인것을 바꿔주기 위해서 입니다.

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

이거는 그냥 문제에서 주어지는 대로 움직이는 범위를 정의한 배열입니다. 6개의 방향이있기때문에 정의해주는것입니다.

while (!q.isEmpty()) {
	int[] xy = q.poll();
	int z = xy[0];
	int x = xy[1];
	int y = xy[2];

	for (int i = 0; i < dx.length; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		int nz = z + dz[i];
		if (nx >= 0 && ny >= 0 && nz >= 0
				&& nx < n && ny < m && nz < h) {
			if (box[nz][nx][ny] == 0) {
				box[nz][nx][ny] = box[z][x][y] + 1;
				q.add(new int[] {nz, nx, ny});
			}
		}
	}
}

본격적인 bfs 입니다. box배열에는 몇번째로 접근이 되는지를 depth + 1을 해주는 것입니다. 0인경우에만 접근해주면 되기 때문에 넘나 쉬움..

private static int validate() {
	int result = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < m; k++) {
				if (box[i][j][k] == 0) {
					return -1;
				}
				result = Math.max(result, box[i][j][k]);
			}
		}
	}
	return result - 1;
}

그런다음에 배열이 모두 접근하였는지를 비교하겠습니다.
depth는 앞서서 box배열에 넣어놨기 때문에 가장 큰 값으로 넣어주면 그 값이 문제어서 원하는 최소 일수가 됩니다. -1을 해주는 이유는 처음부터 배열에 1부터 정의되었기 때문에 이값을 없에주기 위함입니다.

전체 코드

전체 코드