[BOJ/7569] 토마토, c++

2021. 5. 6. 17:15·DEV/PS

www.acmicpc.net/problem/7569

 

7569번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,

www.acmicpc.net

한줄 후기 : 방울 토마토 먹고 싶다.

acmicpc.net/problem/7576

 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

이 문제랑 똑같다. 

대신 7569 번은 3차원 공간에서 토마토가 존재한다고 생각하면 됨.

그래서 그냥 3차원 배열을 만들어줬다.

tomato[H][N][M] 이런식으로 저장해줌.

주의해야할게 당연히 M 이 행이고 N이 열로 들어올 줄 알았는데 반대였다.

 

//AC
//BOJ 7569 토마토
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define SIZE 101
using namespace std;
int day[SIZE][SIZE][SIZE];
int tomato[SIZE][SIZE][SIZE];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
int dh[2] = { 1, -1 };
struct Index{
	int h, m, n;
};
int main(){
	int M, N, H;
	queue<Index> q;
	cin >> N >> M >> H;
	int tmp = 0;
	while(tmp < H){
		for(int i=0; i<M; i++){
			for(int j=0; j<N; j++){
				day[tmp][i][j] = -1;
				scanf("%d", &tomato[tmp][i][j]);
				if(tomato[tmp][i][j] == 1){
					day[tmp][i][j] = 0;
					q.push({tmp, i, j});
				}
			}
		}
		tmp += 1;
	}
	while(!q.empty()){
		int h1 = q.front().h;
		int m1 = q.front().m;
		int n1 = q.front().n;
		q.pop();
		for(int i=0; i<4; i++){
			int nx = m1+dx[i];
			int ny = n1+dy[i];
			if(nx < 0 || ny < 0 || nx >= M || ny >= N)	continue;
			if(tomato[h1][nx][ny] == 0 && day[h1][nx][ny] == -1){
				day[h1][nx][ny] = day[h1][m1][n1] + 1;
				q.push({h1, nx, ny});
			}
		}
		for(int i=0; i<2; i++){
			int nh = h1+dh[i];
			if(nh < 0 || nh >= H)	continue;
			if(!tomato[nh][m1][n1] && day[nh][m1][n1] == -1){
				day[nh][m1][n1] = day[h1][m1][n1] + 1;
				q.push({nh, m1, n1});
			}
		}
	}
	int ans = 0;
	for(int i=0; i<H; i++){
		for(int j=0; j<M; j++){
			for(int k=0; k<N; k++){
				ans = max(ans, day[i][j][k]);
				if(day[i][j][k] == -1 && !tomato[i][j][k]){
					printf("-1");
					return 0;
				}
			}
		}		
	}
	printf("%d" , ans);
	return 0;
}

 

복잡해 보이지만 사실 간단한 bfs 문제라 생각하면 된다.

queue를 이용할건데, 여기서 day 배열은 해당 위치 토마토가 익을 때 까지 걸린 day를 의미한다.

구조체를 이용해 위치 index를 저장할 것이다. 

같은 높이에 있는 토마토는 상하 좌우만 보면 되니 dx, dy 배열을 세팅해준다.

dh 배열을 새로 만들어줬는데 이는 다른 높이, 즉 위, 아래 인덱스를 계산해줄 배열이다.

 

미리 익어있는 토마토는 입력 받을 때, day를 0으로 세팅하고 큐에 넣어 두었다.

큐가 비어있지 않다면 계속해서 상,하,좌,우,위,아래를 돌면서 day = -1이고 (아직 안익은=방문 X) and tomato = 0 (토마토가 존재하는 칸) 이라면 해당 위치 day = 현재 위치 day + 1 해주면 된다.

모든 탐색이 끝나면, 전체적으로 안익은 토마토가 존재하는지 확인하면서 (만약 존재한다면 바로 -1출력!)

max answer를 갱신해준다. 

 

7576 문제랑 거의 비슷한데 다른 높이 토마토 상자를 한번 더 계산해줘야하는 문제였다.

7576을 먼저 풀고 풀면 쉬울 듯  

저작자표시 비영리 변경금지 (새창열림)

'DEV > PS' 카테고리의 다른 글

[BOJ/20127] Y-수열, C++  (0) 2021.05.14
제 1회 SMUPC 숙명 프로그래밍 경진대회 참가 후기  (4) 2021.05.09
[BOJ/2467] 용액  (0) 2021.05.02
[BOJ/1339] 단어 수학, c++  (0) 2021.04.30
[BOJ/2116] 주사위 쌓기, c++  (0) 2021.04.23
'DEV/PS' 카테고리의 다른 글
  • [BOJ/20127] Y-수열, C++
  • 제 1회 SMUPC 숙명 프로그래밍 경진대회 참가 후기
  • [BOJ/2467] 용액
  • [BOJ/1339] 단어 수학, c++
jobchae
jobchae
말하는 감자지만, 코드를 끄적이는 Node.js 백엔드 개발자입니다.
  • jobchae
    JOBCHAE
    jobchae
  • 전체
    오늘
    어제
    • 🚀 JOBCHAE (177)
      • DEV (146)
        • PS (108)
        • Node.js (12)
        • React (3)
        • docker (1)
        • 잡다한 개발 일지 (20)
        • injection (1)
        • CI CD (0)
        • JS, TS (1)
      • 축구 (0)
      • 일상 (19)
      • 영화 (3)
      • 음악 (8)
  • 블로그 메뉴

    • 💻 Github
    • 🙋🏻 Linkedin
    • 📖 방명록
  • 링크

    • PS Github
  • 공지사항

  • 인기 글

  • 태그

    렛츠락페스티벌
    알고리즘
    슬랙
    백준
    슬랙봇
    slack
    Express
    node.js
    GitHub
    react
    Nest
    boj
    DP
    typescript
    mongoDB
    SOPT
    DFS
    앱잼
    nodejs
    이분탐색
    우선순위큐
    솝트
    일상
    회고
    리액트
    aws
    BFS
    위상정렬
    Nest.js
    PS
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
jobchae
[BOJ/7569] 토마토, c++
상단으로

티스토리툴바