백준 7576

1. 문제이해

 

 

2. 문제분석

(1,1) ~ (M, N) 까지 이중 for문을 돌면서 1(토마토가 익은 지점)이 있으면 그 지점을 기준으로 삼아서 주변에 0(익지 않은 토마토)를 1로 만드는 과정을 수행하면 되는데 익은 토마토로 만드는 과정이 최대 N*M번 수행될 수 있으니 O(N*N*M*M)의 시간복잡도가 걸리게 되어서 시간 내로 해결이 불가능하다.

예시를 들자면 n=2, m=3 일때 토마토가 익은지점까지 찾아가는데 4번(n*m)이 걸리고 토마토가 익은지점에서 인접한 익지 않은 토마토를 큐에 push, pop 해서 모두 익은 토마토로 만드는 과정이 4번(n*m)걸린다.

 

그래서 1(토마토가 익은)인 지점을 모두 큐에 넣고 BFS를 수행하는 것이다.

그리고 board 배열(익은 토마토, 익지않은 토마토, 벽)과 dist 배열(익은 토마토로 구성된 곳)을 만들어서 구분시킨다.

board에서 1인 지점을 pop할 때 dist 배열에서 상하좌우로 익지않은 토마토(-1)를 체크하는데 0(벽)이 있으므로 큐에 push할 데이터가 없게 되므로 큐는 종료된다. 

dist 배열에서 0을 벽으로 설정한 이유는 Int의 초기값인 0을 사용했고 토마토가 익는 횟수가 증가할수록 0보다 커지기 때문에 익지 않은 토마토는 -1로 설정했다. 

(상하좌우로 익지 않은 토마토를 확인할 때 -1인 것만 체크하기 위해서, 0 또는 1이상이면 벽이거나 토마토가 익는 최소횟수이기 때문)

 

"이러한 문제 풀이 방법을 어떻게 생각해냈을까?

처음에는 생각하기 힘들겠지만 응용된 문제풀이 방법을 계속 습득하다 보면 비슷한 응용문제도 풀 수 있을꺼라 생각함"

 

 

3. 코드

#include <iostream>
#include <utility>
#include <queue>
using namespace std;
#define X first
#define Y second 

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

int board[1002][1002];
int dist[1002][1002];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);    

    // 1.입력
    int m, n; // m(행:y), n(열:x)
    cin >> m >> n;
    queue<pair<int, int>> Q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
            if (board[i][j] == 1) {
                Q.push({ i,j });
            }
            if (board[i][j] == 0) {
                dist[i][j] = -1;
            }
        }
    }    

    // 2.로직
    // 1인 지점을 모두 큐에 넣어줌
    // 0(토마토가 익지 않음)인 지점은 dist 배열에 값을 -1로 변경
    // 왜냐하면 1인 지점이랑 인접한 0은 모두 1이상으로 바뀌기 때문에 모든 토마토를 익게 만들었을 때 익지 못한 토마토를 구별하기 위해서 
    while (!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (dist[nx][ny] >= 0) continue; // -1이면 모두 0(토마토가 익지 않음)이기 때문에 조건이 성립하지 않음
            dist[nx][ny] = dist[cur.X][cur.Y] + 1; // 해당 익지 않은 토마토까지 도달한 횟수
            Q.push({ nx, ny }); // 익지않은 토마토가 익은 토마토로 변경된것을 큐에 넣음
        }
    }

    int minDays = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (dist[i][j] == -1) {
                cout << -1;
                return 0;
            }
            if (dist[i][j] > minDays) {
                minDays = dist[i][j];
            }
        }
    }

    // 3.결과
    cout << minDays;

    

    return 0;
}

 

 

재풀이

 

 

#include<iostream>	
#include<queue>
using namespace std;

int board[1002][1002];
int vis[1002][1002];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int m, n;

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	// 1.입력
	cin >> m >> n; // m(가로), n(세로)
	queue<pair<int, int>> Q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			// 익은 토마토(1)만 큐에 넣음
			if (board[i][j] == 1) {
				vis[i][j] = 1;
				Q.push({ i,j });
			}			
		}
	}

	// 2.로직
	int minDay = 0;
	while (!Q.empty()) {
		pair<int, int> cur = Q.front();
		Q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (board[nx][ny] != 0) continue;
			board[nx][ny] = 1;
			vis[nx][ny] = vis[cur.first][cur.second] + 1;
			minDay = vis[nx][ny]; // 여기 부분이 비효율적인데 만약에 인접한 4곳 모두 익지 않은 토마토인 경우 4번의 연산이 발생
			Q.push({ nx, ny });
		}
	}
	
	// 토마토가 모두 익지 못하는 상태
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 0) {
				cout << -1;
				return 0;
			}
		}
	}

	// 토마토가 이미 모두 익어있는 상태
	if (minDay == 0) {
		cout << 0;
	}
	else { // 토마토가 모두 익기까지의 최초일수
		cout << minDay - 1;
	}	
		
	return 0;
}