경우없는 개발 블로그

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

#문제 해결 방법

슬라이딩 윈도우를 사용하자

#전체 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, d, k, c;
    cin >> N >> d >> k >> c;

    vector<int> sushi(N);
    vector<int> sushiCount(d + 1, 0);  

    for (int i = 0; i < N; i++) {
        cin >> sushi[i];
    }

    int sushiType = 0;
    int maxType = 0;

    for (int i = 0; i < k; i++) {
        if (sushiCount[sushi[i]]++ == 0) {
            sushiType++;
        }
    }

    maxType = sushiType;

    for (int i = 1; i < N; i++) {
        if (--sushiCount[sushi[i - 1]] == 0) {
            sushiType--;
        }

        if (sushiCount[sushi[(i + k - 1) % N]]++ == 0) {
            sushiType++;
        }


        if (sushiCount[c] == 0) {
            maxType = max(maxType, sushiType + 1);
        }
        else {
            maxType = max(maxType, sushiType);
        }
    }

    cout << maxType;

    return 0;
}

#코드 해설

1. 변수 초기화
   • N: 벨트 위에 놓인 접시의 수.
   • d: 초밥의 종류 수.
   • k: 연속해서 먹는 접시의 수.
   • c: 쿠폰에 적힌 초밥 번호.
   • sushi: 벨트 상의 초밥의 정보를 저장하는 벡터.
   • sushiCount: 각 초밥 번호가 현재 선택된 범위 내에서 몇 번 나타났는지를 저장하는 벡터.
   • sushiType: 현재 선택된 범위 내에서의 서로 다른 초밥의 종류 수.
   • maxType: 가능한 최대 종류의 초밥 수.
2. 처음 k개의 초밥 종류 계산
   • 초기에 0번부터 k-1번째 까지의 초밥을 선택한 상태에서의 서로 다른 종류의 초밥 수를 계산합니다.
3. 슬라이딩 윈도우를 사용한 계산
   • 회전 초밥 벨트이므로, N번을 반복하면서 슬라이딩 윈도우 기법을 사용하여 선택 범위를 1칸씩 옮겨가면서 서로 다른 종류의 초밥 수를 계산합니다.
   • 이때, 이전 범위의 첫번째 초밥을 제거하고, 새로운 초밥을 범위에 포함시키면서 선택된 범위 내에서의 서로 다른 초밥의 종류 수를 업데이트 합니다.
   • 또한, 현재 선택된 범위 내에서 쿠폰에 적힌 초밥 번호 c가 없으면, 쿠폰을 사용하여 추가로 1종류의 초밥을 먹을 수 있음을 고려하여 maxType을 업데이트합니다.
4. 결과 출력
   • maxType을 출력합니다. 이 값은 연속해서 k개의 접시를 먹었을 때, 가능한 한 최대의 다양한 종류의 초밥을 먹는 경우의 초밥 종류 수를 나타냅니다.

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

#문제 해결 방법

투 포인터를 사용하자

#전체 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    int st = 0, en = 0;
    int maxLength = 0;
    int curType = 0;

    int alpha[26] = { 0, };

    while (en < s.length()) {
        if (alpha[s[en] - 'a'] == 0) curType++; // 새로운 알파벳 타입을 발견
        alpha[s[en] - 'a']++;

        while (curType > n) { // 허용된 타입을 초과하면 앞에서부터 제거
            if (--alpha[s[st] - 'a'] == 0) curType--;
            st++;
        }

        maxLength = max(maxLength, en - st + 1); // 최대 길이 갱신
        en++;
    }

    cout << maxLength << endl;

    return 0;
}

#코드 설명

1. 변수 설정
   • int st = 0, en = 0; : 투 포인터 알고리즘에서 사용할 시작 포인터(st)와 끝 포인터(en)를 초기화합니다.
   • int maxLength = 0; : 최대 문자열 길이를 저장할 변수입니다.
   • int curType = 0; : 현재 연속된 문자열에서의 알파벳 종류의 수를 저장합니다.
   • int alpha[26] = { 0, }; : a부터 z까지의 알파벳이 현재 연속된 문자열에서 몇 번 나타났는지를 저장하는 배열입니다.
2. 투 포인터 알고리즘
   • while (en < s.length()) : 끝 포인터(en)가 문자열의 길이보다 작은 동안 반복합니다.
     • if (alpha[s[en]-'a'] == 0) curType++; : 끝 포인터가 가리키는 알파벳이 현재 연속된 문자열에 처음 등장하면 알파벳 종류의 수(curType)를 1 증가시킵니다.
     • alpha[s[en]-'a']++; : 해당 알파벳의 등장 횟수를 1 증가시킵니다.
     • while (curType > n) : 알파벳 종류의 수가 N을 초과하면, 시작 포인터를 하나씩 이동시키면서 초과된 알파벳 종류의 수를 줄입니다.
     • maxLength = max(maxLength, en - st + 1); : 최대 문자열 길이를 갱신합니다.
     • en++; : 끝 포인터를 1 증가시킵니다.

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

#문제 간단 정리

위상정렬을 사용해 문제를 풀자.

#전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int main() {
    int T;
    cin >> T;

    while (T--) {
        int N, K;
        cin >> N >> K;

        vector<int> build_time(N + 1, 0);
        vector<int> indegree(N + 1, 0);
        vector<int> result(N + 1, 0);
        vector<vector<int>> adj(N + 1);

        for (int i = 1; i <= N; i++) {
            cin >> build_time[i];
        }

        for (int i = 0; i < K; i++) {
            int X, Y;
            cin >> X >> Y;
            adj[X].push_back(Y);
            indegree[Y]++;
        }

        int W;
        cin >> W;

        queue<int> q;
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                q.push(i);
                result[i] = build_time[i];
            }
        }

        while (!q.empty()) {
            int current = q.front();
            q.pop();

            for (int next : adj[current]) {
                result[next] = max(result[next], result[current] + build_time[next]);
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }

        cout << result[W] << '\n';
    }

    return 0;
}

#코드해설

while (!q.empty()) {
            int current = q.front();
            q.pop();

            for (int next : adj[current]) {
                result[next] = max(result[next], result[current] + build_time[next]);
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }

위상정렬 핵심부분

1. while (!q.empty()) { ... }:
   • 큐 q에는 현재 짓기 시작할 수 있는 건물들의 번호가 저장됩니다. (선행 건물이 없는, 즉 현재 지을 수 있는 건물)
2. int current = q.front(); q.pop();:
   • 큐의 가장 앞에 있는 건물 번호를 가져와 current에 저장하고, 해당 건물 번호를 큐에서 제거합니다.
3. for (int next : adj[current]) { ... }:
   • 현재 건물(current)을 짓고 나서 지을 수 있는 후속 건물들을 순회합니다. 여기서 adj는 인접 리스트로, 각 건물에서 다음에 지을 수 있는 건물들의 목록을 저장하고 있습니다.
4. result[next] = max(result[next], result[current] + build_time[next]);:
   • next 건물을 짓기 시작하기 전까지의 누적 시간을 result[next]에 저장합니다. 여기서 중요한 점은, next 건물을 짓기 시작하는 시간이 여러 경로로 인해 다를 수 있기 때문에 그 중 가장 늦은 시간을 선택해야 합니다. 이를 위해 max 함수를 사용합니다.
5. indegree[next]--;:
   • next 건물로 들어오는 간선의 수(indegree)를 하나 줄입니다. 이는 current 건물이 지어졌기 때문에 next 건물로의 선행 조건이 하나 줄어들었음을 나타냅니다.
6. if (indegree[next] == 0) { q.push(next); }:
   • 만약 next 건물로 들어오는 선행 조건이 모두 해소되었다면 (즉, 모든 선행 건물들이 지어졌다면), next 건물도 지을 수 있게 되므로 큐 q에 추가합니다.

이 알고리즘을 통해 선행 건물들의 건설 완료 시간을 고려하여 각 건물을 건설하는 데 필요한 최소 시간을 result 배열에 저장할 수 있습니다.

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

이 문제는 Dynamic Programming (DP)을 사용하여 해결할 수 있는 문제입니다. 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)를 찾는 문제입니다.

#발상
주어진 수열 A에서, 각 위치에서 그 위치를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 찾아보자는 것이 발상의 기본입니다. 이렇게 각 위치마다의 LIS 길이를 구하면, 그 중 최대값이 전체 수열 A의 LIS 길이가 됩니다.

#해설
초기화: D[i] 배열은 i번째 원소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 저장합니다. 초기에는 모든 원소의 값이 1입니다. 왜냐하면, 각 원소 자체만으로 길이 1의 증가하는 부분 수열을 이룰 수 있기 때문입니다.

DP 수행: i번째 원소에 대해, 0부터 i-1번째 원소까지 비교를 수행합니다. 만약 A[j] < A[i]이면, j번째 원소가 i번째 원소 앞에 올 수 있으므로, D[i] = max(D[i], D[j] + 1)를 수행합니다. 이는 i번째 원소 앞에 올 수 있는 j번째 원소들 중, 가장 긴 증가하는 부분 수열에 i번째 원소를 추가하는 것입니다.

결과 출력: D[i] 배열 중 가장 큰 값을 출력합니다. 이 값이 주어진 수열 A의 가장 긴 증가하는 부분 수열의 길이입니다.

#코드 설명
vector<int> A(1001)와 vector<int> D(1001,1)는 각각 수열 A와 각 위치의 LIS 길이를 저장합니다.
수열 A의 크기 N을 입력받고, N개의 원소를 A에 저장합니다.
이중 반복문을 통해 각 위치에서 LIS 길이를 계산합니다.
계산된 LIS 길이 중 최대값을 MAX 변수에 저장합니다.
MAX 값을 출력합니다.
이 방법을 통해, O(N^2)의 시간 복잡도로 문제를 해결할 수 있습니다.

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

#문제 간단 정리

dp 를 쓰자

주의할건 dp 배열의 초기값을 높게 설정해 줘야 한다

최소값을 고르는거기 때문에 0이 설정되어 있다면 최소값으로 0이 선택되기 때문이다.

#전체 코드

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

using namespace std;


int main() {

    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;
    vector<int> card(n + 1);
    vector<int> d(n + 1,123456789);
    for (int i = 1; i <= n; i++) {
        cin >> card[i];
    }
    d[0] = 0;
    d[1] = card[1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <=i; j++) {
            d[i] = min(d[i], d[i - j] + card[j]);
        }
    }

    cout << d[n];

    return 0;
}

#코드 설명

이 문제는 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있는 문제입니다. 주어진 코드도 동적 계획법을 사용하여 문제를 해결하고 있습니다. 문제에서 요구하는 것은 주어진 카드 팩의 가격을 바탕으로 N개의 카드를 최소 비용으로 구매하는 방법을 찾는 것입니다.

주어진 코드의 주요 부분을 설명하겠습니다:

vector<int> card(n + 1);와 vector<int> d(n + 1,123456789);는 각각 카드 팩의 가격과 각 개수의 카드를 구매하는데 필요한 최소 비용을 저장하는 배열입니다.

d[0] = 0;와 d[1] = card[1];은 초기값 설정입니다. 0개의 카드를 구매하는데는 비용이 없고, 1개의 카드를 구매하는데는 card[1]의 비용이 듭니다.

이중 for문을 사용하여 각 개수의 카드를 구매하는데 필요한 최소 비용을 계산합니다. 여기서 d[i] = min(d[i], d[i - j] + card[j]);는 i개의 카드를 구매하는데 필요한 최소 비용을 구하는 식입니다. i-j개의 카드를 구매하는데 드는 최소 비용에 j개 카드 팩의 가격을 더한 값과 현재의 d[i] 값을 비교하여 더 작은 값을 d[i]에 저장합니다.

최종적으로 cout << d[n];을 통해 N개의 카드를 구매하는데 필요한 최소 비용을 출력합니다.

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

#전체 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
vector<int> tree[51];
int check[51];
int leaf = 0;
int wither;
int root;

void findLeaf(int node ) {
    check[node] = true;
    
    if (node == wither) return;

    bool isLeaf = true;

    for (int i = 0; i < tree[node].size(); i++) {
        int nextNode = tree[node][i];
        if (check[nextNode] != true && nextNode != wither) {
            isLeaf = false;
            findLeaf(nextNode);
        }
    }

    if (isLeaf) leaf++;

}


int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;     cin >> n;

    for(int i=0; i<n; i++){
        int input; cin >> input;
        if (input == -1) {
            root = i;
        }
        else {
            tree[input].push_back(i);
        }

    }
    cin >> wither;
    
    findLeaf(root);

    cout << leaf << "\n";


    return 0;
}

벡터로 트리를 구현했다.

리프는 dfs를 사용해서 찾았다

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

#문제 간단 정리

문제 풀이 전략
문제의 목적은 주어진 규칙에 따라 연속된 집들을 서로 다른 색으로 칠하는 최소 비용을 찾는 것입니다. 이러한 유형의 문제는 동적 프로그래밍(dynamic programming, DP)을 사용하여 해결할 수 있습니다.

문제를 해결하는 전략은 다음과 같습니다:

먼저, 각 집을 칠할 때의 비용을 2차원 배열에 저장합니다.
그런 다음, 다른 색상 조합에 대해 이전 집들까지의 최소 비용을 저장하는 또 다른 2차원 배열을 만듭니다.
각 집에 대해 가능한 색상을 선택하고, 선택한 색상을 제외한 이전 집의 두 색상 중 최소 비용을 현재 집의 비용에 더합니다.
모든 집을 확인한 후, 마지막 집에서 가능한 최소 비용을 찾습니다

#전체 코드

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

using namespace std;


int main() {
	int n; cin >> n;
	int house_cost[1001][3] = { 0 };
	int result[1001][3] = { 0, };

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> house_cost[i][j];
		}
	}

	result[0][0] = house_cost[0][0];
	result[0][1] = house_cost[0][1];
	result[0][2] = house_cost[0][2];

	for (int i = 1; i <= n; i++) {
		result[i][0] = min(result[i-1][1],result[i-1][2]) + house_cost[i][0];
		result[i][1] = min(result[i - 1][0], result[i - 1][2]) + house_cost[i][1];
		result[i][2] = min(result[i - 1][0], result[i - 1][1]) + house_cost[i][2];

	}
	int min = 123456789;
	for (int i = 0; i < 3; i++) {
		if (result[n][i] < min) {
			min = result[n][i];
		}
	}
	cout << min << endl;
}

코드 해설
코드는 위에서 설명한 전략을 따르며, 주요 부분을 분석하겠습니다.

cpp
Copy code
int n; cin >> n;
int house_cost[1001][3] = { 0 };
int result[1001][3] = { 0, };
여기서 n은 집의 수를 나타내며, house_cost 배열에 각 집을 칠하는 비용을 저장합니다. result 배열은 각 집에 대한 최소 비용을 저장할 배열입니다.

cpp
Copy code
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
cin >> house_cost[i][j];
}
}
이 부분은 각 집을 칠하는 비용을 입력 받아 house_cost 배열에 저장하는 코드입니다.

cpp
Copy code
result[0][0] = house_cost[0][0];
result[0][1] = house_cost[0][1];
result[0][2] = house_cost[0][2];
여기에서 첫 번째 집의 최소 비용을 각 색상의 비용으로 초기화합니다.

cpp
Copy code
for (int i = 1; i <= n; i++) {
result[i][0] = min(result[i-1][1],result[i-1][2]) + house_cost[i][0];
result[i][1] = min(result[i - 1][0], result[i - 1][2]) + house_cost[i][1];
result[i][2] = min(result[i - 1][0], result[i - 1][1]) + house_cost[i][2];
}
이 반복문은 동적 프로그래밍을 통해 각 집에서 가능한 최소 비용을 계산합니다. 현재 집의 각 색상에 대해 가능한 최소 비용을 찾기 위해 이전 집의 두 색상 중 최소 비용을 현재 집의 비용에 더합니다.

cpp
Copy code
int min = 123456789;
for (int i = 0; i < 3; i++) {
if (result[n][i] < min) {
min = result[n][i];
}
}
cout << min << endl;
마지막으로, 마지막 집에서 가능한 최소 비용을 찾고 출력합니다.

주의사항
반복문의 범위를 주의해야 합니다. for (int i = 1; i <= n; i++)에서 i는 n까지 돌아야 하지만, 배열 인덱스는 0부터 시작하므로 house_cost와 result 배열에 접근할 때 i-1을 사용해야 합니다.

cpp
Copy code
for (int i = 1; i < n; i++) { // n까지가 아니라 n-1까지
...
result[i][0] = min(result[i-1][1], result[i-1][2]) + house_cost[i-1][0];
...
}
그리고 최종 결과를 찾을 때, result[n][i] 대신 result[n-1][i]를 사용해야 합니다.

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

#전체 코드

#include <iostream>
#include <algorithm>

using namespace std;


int main() {

    
    string A, B;
    cin >> A >>  B;

    int ans = 0;

    int B_index = B.length() - 1;
    for (int i = A.length()-1; i >= 0; i--) {
        if (A[i] == B[B_index]) {
            B_index --;
        }
        else ans++;

    }

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    if (A == B) cout << ans;
    else cout << -1;



    return 0;
}

문제 해설
문제는 2×n 크기의 직사각형을 1×2 또는 2×1 크기의 타일로 채울 수 있는 방법의 수를 찾는 것입니다. 그러나 찾은 수가 매우 클 수 있으므로, 10,007로 나눈 나머지를 출력해야 합니다.

코드 설명
이 문제를 해결하기 위해 동적 프로그래밍(DP)이라는 방법을 사용하고 있습니다. 아래에서 코드의 각 부분에 대해 설명하겠습니다:

cpp
Copy code
int n; cin >> n;

int tile[1001] = { 0 };
위에서는 n을 입력 받고, 최대 크기가 1001인 배열을 초기화하고 있습니다. 배열 tile은 각 인덱스에서 가능한 타일링 방법의 수를 저장할 것입니다.

cpp
Copy code
tile[0] = 1;
tile[1] = 1;
tile[2] = 2;
2×0, 2×1, 2×2 크기의 직사각형을 타일로 채우는 방법의 수는 각각 1, 1, 2가 됩니다. 이는 초기 조건으로 설정됩니다.

cpp
Copy code
for (int i = 3; i <= n; i++) {
tile[i] = (tile[i - 1] + tile[i - 2])%10007;
}
이 반복문은 DP 접근법의 핵심 부분입니다. 각 i에 대해 (i-1)과 (i-2)에서 가능한 타일링 방법의 수의 합을 구하며, 이를 10,007로 나눈 나머지를 저장합니다. 이는 2×i 크기의 직사각형을 채우는 마지막 부분이 2×1 또는 1×2 타일로 채워지는 두 가지 경우를 고려한 것입니다.

cpp
Copy code
cout << tile[n];
마지막으로, 2×n 크기의 직사각형을 채울 수 있는 방법의 수를 출력합니다. 이 값은 위의 반복문에서 tile[n]에 저장되어 있습니다.

결론
이 코드는 동적 프로그래밍을 사용하여 문제를 효율적으로 해결합니다. 단계별로 이전 결과를 이용해 현재 문제를 해결함으로써, 최종적으로 원하는 크기의 직사각형에 대한 해결책을 찾을 수 있습니다.

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

#문제 간단 정리

문제의 핵심은 A 문자열에서 한 문자를 선택하여 문자열의 가장 앞으로 가져오는 방식으로 B 문자열을 만드는 것입니다. 그러기 위해 최소한으로 문자열을 바꿔야 하는 횟수를 찾아야 합니다. 만약 A 문자열을 B 문자열로 변경할 수 없는 경우 -1을 출력해야 합니다.

#전체 코드

#include <iostream>
#include <algorithm>

using namespace std;


int main() {

    
    string A, B;
    cin >> A >>  B;

    int ans = 0;

    int B_index = B.length() - 1;
    for (int i = A.length()-1; i >= 0; i--) {
        if (A[i] == B[B_index]) {
            B_index --;
        }
        else ans++;

    }

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    if (A == B) cout << ans;
    else cout << -1;



    return 0;
}

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

#문제 간단 정리

이 문제는 주어진 토마토의 상태에 따라 모든 토마토가 익게 되는 최소 일수를 찾는 문제입니다. 문제에서 요구하는 답을 찾기 위해 BFS(Breadth-First Search) 탐색 알고리즘을 사용합니다.

#전체 코드

#include <iostream>
#include <queue>
using namespace std;
int a[1000][1000];
int d[1000][1000];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

struct tomato {
    int x, y;
};

int main() {
    int n, m;
    cin >> m >> n;
    queue<tomato> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            d[i][j] = -1;
            if (a[i][j] == 1) {
                q.push({i,j});
                d[i][j] = 0;
            }
        }
    }
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (a[nx][ny] == 0 && d[nx][ny] == -1) {
                    d[nx][ny] = d[x][y] + 1;
                    q.push({nx,ny});
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (ans < d[i][j]) {
                ans = d[i][j];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 0 && d[i][j] == -1) {
                ans = -1;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

#코드설명

코드 설명

• 변수 선언
  • a[1000][1000]: 각 토마토의 초기 상태를 저장하는 2D 배열
  • d[1000][1000]: 각 토마토가 익게 되는 데 걸리는 일수를 저장하는 2D 배열. 초기값은 -1로 설정
  • dx[], dy[]: 토마토의 인접한 위치를 찾기 위해 현재 위치에 더할 값들을 저장하는 배열
  • tomato: 토마토의 위치를 나타내는 구조체
• 입력 받기
  • m, n: 상자의 가로와 세로 크기
  • 상자의 토마토 상태를 입력 받으면서, 이미 익어 있는 토마토의 위치를 큐에 넣고, 해당 위치의 d[][] 값을 0으로 설정합니다.
• BFS 탐색
  • BFS 탐색을 시작합니다. 큐가 비어있지 않은 동안, 현재 토마토의 위치에서 인접한 네 방향을 확인하며 다음을 수행합니다:
    • 인접한 위치가 상자 내부에 있는지 확인합니다.
    • 인접한 위치의 토마토가 아직 익지 않았고, 방문하지 않은 상태라면, 현재 토마토가 익는 데 걸린 일수에 1을 더한 값을 인접한 위치의 토마토가 익는 데 걸리는 일수로 설정합니다.
    • 인접한 위치의 토마토를 큐에 넣습니다.
• 결과 찾기
  • BFS 탐색이 끝나면, d[][] 배열에서 가장 큰 값을 찾아 ans에 저장합니다. 이 값이 모든 토마토가 익게 되는 데 필요한 최소 일수입니다.
  • 하지만, 상자 안에 아직 익지 않은 토마토가 있는지 확인하고, 있다면 -1을 출력해야 합니다. 이를 위해 a[][] 배열을 탐색하며 아직 익지 않은 토마토가 있는지 확인합니다. 익지 않은 토마토가 있으면 ans 값을 -1로 설정합니다.
• 결과 출력
  • ans 값을 출력합니다.

이 코드는 BFS 탐색을 사용하여 모든 토마토가 익게 되는 최소 일수를 효율적으로 찾습니다.