정범의 프로그래밍 블로그 입니다.

7 분 소요

문제

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

문제내용

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

sample

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

예제 입력 1

5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

예제 입력 2

-1


문제풀이

문제해설

  • 토마토를 보관한 상자에서 토마토들이 며칠이 지나면 모두 익는지, 그 최소 일자를 구하는 문제입니다.
    • 백준 7576 토마토 문제와 유사한 문제입니다.
    • 차이점은 보관 상자가 2차원 배열에서 3차원 배열로 생각해야 하는 점입니다.

생각할 점

  • 3차원 배열이기 때문에 방향 배열과 좌표도 변화가 필요합니다.

3차원 배열 주의점

  • 3차원 배열은 면, 행, 열로 구성됩니다.
  • 3차원 배열의 첨자의 범위는 0 ~ (면 개수-1), 0 ~ (행 개수-1), 0 ~ (열 개수-1) 입니다.
  • 여기서 주의할 점은 배열에 접근하려면 arr[z][x][y]로 적어야 하는데 실수로 arr[x][y][z]로 적을 수 있습니다.

방향 배열

  • 3차원 문제의 경우 dx, dy, dz로 표현이 가능합니다. 
    int dz[6] = { 0,0,0,0,-1,1 }; // 면 방향 배열
int dx[6] = { -1,1,0,0,0,0 }; // 행 방향 배열
int dy[6] = { 0,0,-1,1,0,0 }; // 열 방향 배열

3차원 좌표

<pair<pair<int, int>,int>>
  • 해당 방법으로 3차원 좌표를 표현할 수 있습니다.
  • 하지만 직관적이지 않아 실수할 유려가 있어 직접 클래스로 만들어서 사용하기로 했습니다.
class Position {
private:
	int posz;
	int posx;
	int posy;
	
public:

	Position(int z, int x, int y) {
		posz = z;
		posx = x;
		posy = y;
	}

	int getPosz() { return posz; }
	int getPosx() { return posx; }
	int getPosy() { return posy; }
	
};


코드 리뷰

헤더 선언

#include <iostream>
#include <queue>
#include <algorithm>
  • “iostream” 헤더는 입출력을 사용하기 위해서 선언합니다.
  • “queue” 헤더는 bfs에 사용할 큐를 사용하기 위해서 선언합니다.
  • “algorithm” 헤더는 max 함수를 사용하기 위해서 선언합니다.

변수 선언

int N, M, H; // 상자 크기
int map[100][100][100]; // 토마토 보관 상자
int visited[100][100][100]; // 방문 체크
int days[100][100][100]; // 토마토 익은 날짜

int dz[6] = { 0,0,0,0,-1,1 }; // 면 방향 배열
int dx[6] = { -1,1,0,0,0,0 }; // 행 방향 배열
int dy[6] = { 0,0,-1,1,0,0 }; // 열 방향 배열

int result = -1; // 결과 출력
  • 상자의 세로 크기 N, 가로 크기 M, 높이 H
  • 토마토 보관 상자 map[100][100][100]
  • 방문 체크 visited[100][100][100]
  • 토마토 익은 날짜 모음 days[100][100][100]
  • 6방향 배열 dx[6], dy[6], dz[6]
  • 토마토 익은 최종 날짜 result

bfs 설명1

queue<Position> q; // bfs에 사용할 큐

// 익은 토마토를 중심으로 탐색
for (int i = 0; i < H; i++) {
	for (int j = 0; j < N; j++) {
		for (int k = 0; k < M; k++) {
			if (map[i][j][k] == 1) {
				q.push(Position(i,j,k));
			}	
		}
	}
}
  • 직접 선언한 Position 클래스를 처리하는 큐 선언합니다.
  • 여러 점을 탐색할 경우는 초기 단계에서 큐에 삽입하는게 효율적입니다.
    • 점과 점이 모인 영역을 탐색할 때는 이중 for문을 사용합니다.
    • 여러 점을 탐색할 때 이중 for문을 사용하면 시간 초과가 발생할 수 있습니다.

bfs 설명2(while문)

현재 좌표 가져오기

// 현재 좌표
int z = q.front().getPosz();
int x = q.front().getPosx();
int y = q.front().getPosy();

// 현재 좌표 큐에서 제거
q.pop();
  • 현재 좌표를 x, y, z로 선언합니다.
  • 다음 좌표를 가져오기 위해 현재 좌표를 큐에서 제거합니다.

6방향 이동

// 6방향(상, 하, 좌, 우, 전, 후) 이동
for (int i = 0; i < 6; i++) {
    // 다음 방문 좌표
	int next_z = z + dz[i];
	int next_x = x + dx[i];
	int next_y = y + dy[i];

    // ~~ 중략 ~~
}
  • 6방향으로 이동해서 다음 방문 좌표 next_x, next_y, next_z를 선업합니다.

보관 상자 범위 검사

int rangez = 0 <= next_z && next_z < H;
int rangex = 0 <= next_x && next_x < N;
int rangey = 0 <= next_y && next_y < M;
			
if (!(rangex && rangey && rangez)) continue;
  • 다음 방문 좌표가 주어진 범위에서 벗어났는지 검사합니다.
    • 범위에 벗어나면 다음 반복으로 넘어갑니다.

익지 않은 토마토와 방문하지 않은 곳 탐색

// 익지 않은 토마토가 아니면 제외
if (map[next_z][next_x][next_y] != 0) continue;

// 방문한 곳은 제외
if (visited[next_z][next_x][next_y] != 0) continue;
  • 익지 않은 토마토가 아니고 방문한 곳은 다음 방문으로 넘어가게 합니다.
  • 주의할 점은 arr[z][x][y]입니다.

익은 토마토를 찾았을 경우

visited[next_z][next_x][next_y] = 1; // 방문체크
q.push(Position(next_z, next_x, next_y)); // 다음 방문 큐에 삽입
days[next_z][next_x][next_y] = days[z][x][y] + 1; // 날짜 증가
  • 익은 토마토를 찾으면 먼저 방문 체크를 합니다.
  • 다음 방문 좌표로 큐에 삽입합니다.
  • 날짜를 증가합니다.

결과 출력

// 익지 못한 토마토를 찾았을 때 -1 출력
// 최대 익은 날짜를 구한다.
for (int i = 0; i < H; i++) {
	for (int j = 0; j < N; j++) {
		for (int k = 0; k < M; k++) {
			if (map[i][j][k] == 0 && visited[i][j][k] == 0) {
				cout << -1;
				return 0;
			}
			result = max(days[i][j][k], result);
		}
	}
}

// 출력
cout << result;
  • bfs가 끝난 후 익지 않은 토마토에 방문하지 않은 곳이 있다면 -1을 출력하고 리턴해서 프로그램을 종료합니다.
  • 가장 큰 값이 완료한 날짜이기 때문에 max함수를 사용해서 최종 날짜를 구하고 출력합니다.


전체코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

// 좌표 클래스
class Position {
private:
	int posz;
	int posx;
	int posy;
	
public:

	Position(int z, int x, int y) {
		posz = z;
		posx = x;
		posy = y;
	}

	int getPosz() { return posz; }
	int getPosx() { return posx; }
	int getPosy() { return posy; }
	
};

int N, M, H; // 상자 크기
int map[100][100][100]; // 토마토 보관 상자
int visited[100][100][100]; // 방문 체크
int days[100][100][100]; // 토마토 익은 날짜

int dz[6] = { 0,0,0,0,-1,1 }; // 면 방향 배열
int dx[6] = { -1,1,0,0,0,0 }; // 행 방향 배열
int dy[6] = { 0,0,-1,1,0,0 }; // 열 방향 배열

int result = -1; // 결과 출력

// bfs 함수
void bfs() {

	queue<Position> q; // bfs에 사용할 큐

	// 익은 토마토를 중심으로 탐색
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++) {
				if (map[i][j][k] == 1) {
					q.push(Position(i,j,k));
				}
				
			}
		}
	}

	while (!q.empty()) {
		// 현재 좌표
		int z = q.front().getPosz();
		int x = q.front().getPosx();
		int y = q.front().getPosy();
		

		// 현재 좌표 큐에서 제거
		q.pop();

		// 6방향(상, 하, 좌, 우, 전, 후) 이동
		for (int i = 0; i < 6; i++) {
			// 다음 방문 좌표
			int next_z = z + dz[i];
			int next_x = x + dx[i];
			int next_y = y + dy[i];
			
			// 상자 범위 검사
			int rangez = 0 <= next_z && next_z < H;
			int rangex = 0 <= next_x && next_x < N;
			int rangey = 0 <= next_y && next_y < M;
			
			if (!(rangex && rangey && rangez)) continue;

			// 익지 않은 토마토가 아니면 제외
			if (map[next_z][next_x][next_y] != 0) continue;

			// 방문한 곳은 제외
			if (visited[next_z][next_x][next_y] != 0) continue;

			visited[next_z][next_x][next_y] = 1; // 방문체크
			q.push(Position(next_z, next_x, next_y)); // 다음 방문 큐에 삽입
			days[next_z][next_x][next_y] = days[z][x][y] + 1; // 날짜 증가

		}

	}
	
}

int main() {

	// 상자 크기 입력
	cin >> M >> N >> H;

	// 상자 내용 입력
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++) {
				cin >> map[i][j][k];
			}
		}
	}

	// bfs 탐색
	bfs();

	// 익지 못한 토마토를 찾았을 때 -1 출력
	// 최대 익은 날짜를 구한다.
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++) {
				if (map[i][j][k] == 0 && visited[i][j][k] == 0) {
					cout << -1;
					return 0;
				}
				result = max(days[i][j][k], result);
			}
		}
	}

	// 출력
	cout << result;

	return 0;
}


참조

카테고리:

업데이트:

참고

투 포인터 공부

3 분 소요

투 포인터 두 개의 포인터를 만들어서, 각각이 가리키는 원소에 의미를 부여하여 요구하는 문제를 해결하는 알고리즘입니다. 정확히는 배열이나 리스트에서 두 개의 포인터를 사용하여 특정 조건을 만족하는 구간을 효율적으로 탐색하는 알고리즘입니다. 일반적으로 정렬되어 있을 때 사용...

데이터 타입의 범위와 시간 제한 공부

1 분 소요

코딩 테스트하면서 틀렸습니다와 시간 초과라는 메시지를 받는 경우가 많았습니다. 여러가지 이유가 존재하지만 데이터가 표현할 수 있는 범위를 벗어나서 오답 처리되는 경우가 있었습니다. 예를들어 나무 자르기 문제에서 int형으로 코드를 구현했는데 int형의 범위를 넘어서는 데이터였...

순열과 조합 공부

4 분 소요

이 글은 순열과 조합을 재귀로 구현한 것을 정리한 내용입니다.