Junior-Developer
Home
  • Category (316)
    • 문제풀이 (270)
      • 백준oj (201)
      • 프로그래머스 (53)
      • 명품 자바 프로그래밍(개정4판) (11)
      • 구름 (5)
    • 알고리즘 (6)
    • Node.js (2)
    • 체크리스트 (37)
블로그 내 검색
Home

Junior-Developer

1일 1커밋! 1일 1 백준!

  • 문제풀이/백준oj

    [백준OJ] 7569번 토마토

    2021. 9. 12.

    by. Hyeon-Uk

    반응형

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

     

    7569번: 토마토

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

    www.acmicpc.net


     

     

    풀이

    1. 입력을 받으면서 토마토부분들을 queue에 push해주고, 익지않은 토마토의 개수를 세어준다.

    2. queue에 들어있는 토마토들을 가지고 bfs를 실행해준다. 이때 오늘익은 토마토가 같은날 주변의 다른 익지않은 토마토를 익지 못하게 하기위해, 어제익었던 토마토들만 bfs를 돌리며 날짜를 +1해준다. 또한 토마토들이 익을때마다 익지않은 토마토의 개수를 -1 해준다.

    3. bfs를 끝낸뒤, 익지않은 토마토의 개수가 남아있다면 -1을, 아니라면 날짜를 return 해준다.

     

    시간복잡도

    bfs로 모든 배열을 탐색하므로, O(NMH)가 된다.

     

    반응형

     

    코드

    #include<iostream>
    #include<vector>
    #include<queue>
    #include<algorithm>
    using namespace std;
    
    typedef struct node {
    	int z,x, y;
    }node;
    
    int maze[100][100][100];
    int mv[6][3] = { //위아래, 좌우, 상하로 움직임
    	{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},
    {1,0,0},{-1,0,0}
    };
    int m, n, h;
    int blank;//익지않은 토마토
    queue<node> tomato;
    
    void input() {
    	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 >> maze[i][j][k];
    				if (maze[i][j][k] == 0) blank++;
    				if (maze[i][j][k] == 1) tomato.push({ i,j,k });
    			}
    		}
    	}
    }
    
    bool isIn(int z, int x, int y) {
    	return (z >= 0 && z < h&&x >= 0 && x < n&&y >= 0 && y < m);
    }
    
    int bfs() {
    	int time = 0;
    	while (!tomato.empty()&&blank) {
            //오늘 익은 토마토들이 같은날 다른 토마토를 익게하지 않기위해
            //어제익은 토마토들만을 기준으로 bfs
    		int tsize = tomato.size();
    		for (int i = 0; i < tsize; i++) {
    			int z = tomato.front().z;
    			int x = tomato.front().x;
    			int y = tomato.front().y;
    			tomato.pop();
    
    			for (int d = 0; d < 6; d++) {
    				int nz = z + mv[d][0];
    				int nx = x + mv[d][1];
    				int ny = y + mv[d][2];
    
    				if (isIn(nz, nx, ny) && maze[nz][nx][ny] == 0) {
    					maze[nz][nx][ny] = 1;
    					blank--;
    					tomato.push({ nz,nx,ny });
    				}
    			}
    		}
    		time++;
    	}
    	if (blank) {
    		return -1;
    	}
    	else {
    		return time;
    	}
    }
    
    int main() {
    	input();
    	cout << bfs() << "\n";
    }
    반응형
    저작자표시

    '문제풀이 > 백준oj' 카테고리의 다른 글

    [백준OJ] 8983번 사냥꾼  (0) 2021.09.14
    [백준OJ] 6443번 애너그램  (0) 2021.09.13
    [백준OJ] 9370번 미확인 도착지  (0) 2021.09.11
    [백준OJ] 10799번 쇠막대기  (0) 2021.09.10
    [백준OJ] 4803번 트리  (0) 2021.09.09

    댓글

    관련글

    • [백준OJ] 8983번 사냥꾼 2021.09.14
    • [백준OJ] 6443번 애너그램 2021.09.13
    • [백준OJ] 9370번 미확인 도착지 2021.09.11
    • [백준OJ] 10799번 쇠막대기 2021.09.10
    맨 위로
전체 글 보기
Tistory 로그인
Tistory 로그아웃
로그아웃 글쓰기 관리

Today

Total

Powered by ⓒ Kakao Corp.

Designed by Nana
블로그 이미지
Hyeon-Uk

티스토리툴바