백준 7576번 토마토, 7569번 토마토(3차원 버전)

1. 7576번 토마토
    1-1. 링크
    1-2. 문제 해석
    1-3. 코드 및 해설
2. 7569번 토마토
    1-1. 링크
    1-2. 문제 해석
    1-3. 코드 및 해설

 

 

 

---

 

1. 7576번 토마토

1-1. 링크

7576번: 토마토

 

1-2. 문제 해석

처음에는 "음? 이거 뭐 특별한 로직없이 삼중 포문 쓰면 풀리지 않나?"라고 생각했다.

모든 칸들을 반복문으로 돌면서 상하좌우로 퍼지게하고...

하루가 지날 때마다 다 채워졌는지 체크하면 될 거라고 생각했는데 답은 잘 나오지만 시간 초과가 떴다.

시간 복잡도가 O(n³)가 되면 의심도 좀 해보고 해야 하는데 이 무지성코더를 어찌하면 좋을꼬...

 

아무튼 그래서 이 문제는 BFS를 사용해야 하는 문제이다.

내가 알기론 BFS로 풀 수 있는 문제는 DFS로도 풀 수 있고 그 반대도 가능하다고 알고 있는데

대신 BFS로 풀기 쉬운 문제가 있고 DFS로 풀기 쉬운 문제가 있는데

이건 BFS로 해야 쉽고 DFS는... 상상도 하기 싫다.

 

아무튼 평범한 BFS 문제처럼 Queue에 좌표랑 day를 넣어주었고

익은 토마토가 다른 토마토를 익게 만들 때 카운트를 세어주었다.

N * M = 전체 칸의 개수 = 익은 토마토가 들어있는 칸의 수 + 비어있는 칸 수

이므로 이를 이용해서 토마토가 모두 익지는 못하는 상황인지를 판단했다.

 

1-3. 코드 및 해설

public class _7576_토마토 {
    /*
    * ripen: 익은 토마토의 수
    * empty: 비어있는 칸의 수
    */
	static int M, N, ripen = 0, empty = 0;
	static int[][] box;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static Queue<Pos> queue = new LinkedList<>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		box = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				box[i][j] = Integer.parseInt(st.nextToken());
				if (box[i][j] == 1) {
					queue.add(new Pos(i, j, 0));
					ripen++;
				} else if (box[i][j] == -1) {
					empty++;
				}
			}
		}

		int day = BFS();
		System.out.println((ripen == N * M - empty) ? day : -1);
	}

	public static int BFS() {
		boolean[][] visited = new boolean[N][M];

		while (!queue.isEmpty()) {
			Pos p = queue.poll();

			for (int i = 0; i < 4; i++) {
				int newY = p.y + dy[i];
				int newX = p.x + dx[i];

				if (isMovable(newY, newX) && !visited[newY][newX]) {
					box[newY][newX] = 1;
					visited[newY][newX] = true;
					ripen++;
					queue.add(new Pos(newY, newX, p.day + 1));
				}
			}

			if (queue.isEmpty()) {
				return p.day;
			}
		}

		return Integer.MAX_VALUE; // 사실 여기로 올 일은 없음
	}

	public static boolean isMovable(int y, int x) {
		if (y < 0 || x < 0 || y >= N || x >= M) {
			return false;
		}

		if (box[y][x] == -1 || box[y][x] == 1) {
			return false;
		}

		return true;
	}

	static class Pos {
		int y;
		int x;
		int day;

		public Pos(int y, int x, int day) {
			this.y = y;
			this.x = x;
			this.day = day;
		}
	}
}

BFS에 리턴문이 2개가 있는데 무조건 첫 번째 리턴문으로 빠지기 때문에 두 번째 리턴문은 사실상 의미가 없긴 하다.

적어줘야 해서 적어주었을 뿐...

어떻게 보면 구조상으로 완벽하지 않은 거일 수도 있을 것 같다.

 

BFS문을 멈춰야 하는 상황을 체크할 수 있는 조건만 구해낼 수 있으면

두 번째 리턴문도 필요 없고 ripen을 카운팅 할 필요도 없을 텐데

그 조건을 못 찾아서 위와 같은 방법을 사용했다.

 

2. 7569번 토마토

2-1. 링크

7569번: 토마토

 

2-2. 문제 해석

[목차 1] 문제인 토마토 문제의 3차원 버전이다.

DFS나 BFS로 3차원 문제는 처음 풀어보는 건데 생각보다 간단했다.

 

	static int[][][] box;
                          // 상 하 좌 우 위 아래
	static int[] dy = { -1, 1, 0, 0, 0, 0 };
	static int[] dx = { 0, 0, -1, 1, 0, 0 };
	static int[] dz = { 0, 0, 0, 0, -1, 1 };

2차원 배열이던 box를 3차원으로 늘리고

상하좌우 외에 위아래까지 탐색하기 위해 dz를 추가했다.

 

그리고 그에 맞게 코드를 조금씩 수정하면 된다.

머릿속에서 3차원을 상상해서 그릴 줄 알면 쉽게 풀리는 문제...!

 

1-3. 코드 및 해설

public class _7569_토마토_3차원 {
	static int M, N, H, ripen = 0, empty = 0;
	static int[][][] box;
	static int[] dy = { -1, 1, 0, 0, 0, 0 };
	static int[] dx = { 0, 0, -1, 1, 0, 0 };
	static int[] dz = { 0, 0, 0, 0, -1, 1 };
	static Queue<Pos> queue = new LinkedList<>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		box = new int[H][N][M];

		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) {
						queue.add(new Pos(i, j, k, 0));
						ripen++;
					} else if (box[i][j][k] == -1) {
						empty++;
					}
				}
			}
		}

		int day = BFS();
		System.out.println((ripen == H * N * M - empty) ? day : -1);
	}

	public static int BFS() {
		boolean[][][] visited = new boolean[H][N][M];

		while (!queue.isEmpty()) {
			Pos p = queue.poll();

			for (int i = 0; i < 6; i++) {
				int newZ = p.z + dz[i];
				int newY = p.y + dy[i];
				int newX = p.x + dx[i];

				if (isMovable(newZ, newY, newX) && !visited[newZ][newY][newX]) {
					box[newZ][newY][newX] = 1;
					visited[newZ][newY][newX] = true;
					ripen++;
					queue.add(new Pos(newZ, newY, newX, p.day + 1));
				}
			}

			if (queue.isEmpty()) {
				return p.day;
			}
		}

		return Integer.MAX_VALUE; // 여기로 올 일은 없음
	}

	public static boolean isMovable(int z, int y, int x) {
		if (z < 0 || y < 0 || x < 0 || z >= H || y >= N || x >= M) {
			return false;
		}

		if (box[z][y][x] == -1 || box[z][y][x] == 1) {
			return false;
		}

		return true;
	}

	static class Pos {
		int z;
		int y;
		int x;
		int day;

		public Pos(int z, int y, int x, int day) {
			this.z = z;
			this.y = y;
			this.x = x;
			this.day = day;
		}
	}
}

이전 문제랑 같기 때문에 딱히 설명할 건 없는 것 같다.

다만 삼중 포문이 들어가길래 어? 이거 설마 또 시간 초과 나려나? 싶었는데

문제에서 주어지는 입력의 범위가 이전 문제에선 1000까지였는데 이번엔 100까지라 통과할 수 있었다.

 

 

 

---

💡 느낀 점

• 제발 내가 생각 없이 문제를 풀지 말고 시간 복잡도를 잠깐만이라도 고민해보고 풀었으면 좋겠다...
• DFS가 좋아서 항상 BFS 문제를 피해왔었는데 이번 기회에 이것저것 풀다가 느낀 건데 BFS가 더 편한 것 같기도..
• BFS 문제는 거의 항상 Queue에 좌표 값이랑 moves와 같은 값을 같이 넣는 것 같다. 기억해둬야지...
• 3차원 문제 풀기 전에 쫄았는데 막상 풀어보니 다를 것 없는 듯!

---