경우없는 개발 블로그

#문제 간단 정리

dp 를 사용해서 풀어야한다

#문제 해결 방법

문제 상황

먼저, 문제 상황을 이해해야 합니다. 여기서는 가로로 2칸, 세로로 N칸인 우리가 있고, 사자들을 배치하는 문제입니다. 조건은 다음과 같습니다:

• 사자들은 가로나 세로로 붙어 있을 수 없습니다.
• 사자를 한 마리도 배치하지 않는 경우도 포함합니다.

동적 프로그래밍 이해하기

DP는 큰 문제를 작은 문제로 나누어 푸는 방법입니다. 이 문제에서는 'N번째 칸까지 사자를 어떻게 배치할 수 있는가'를 작은 문제로 삼습니다. 각 칸에 대해 다음과 같은 세 가지 경우를 생각해볼 수 있습니다:

1. 사자를 배치하지 않는 경우.
2. 사자를 첫 번째 칸에만 배치하는 경우.
3. 사자를 두 번째 칸에만 배치하는 경우.

DP 배열 설정

DP를 사용하기 위해 각 상태를 저장할 배열을 설정합니다. dp[N][3] 배열을 사용하며, 여기서 N은 우리의 크기를 나타내고, 두 번째 차원의 크기 3은 위의 세 가지 경우를 나타냅니다.

초기 조건 설정

DP 배열의 초기값을 설정합니다. 첫 번째 칸에 대해 사자를 배치하지 않거나, 첫 번째 칸이나 두 번째 칸 중 하나에만 배치하는 경우는 각각 1가지 방법이 있습니다. 따라서 dp[1][0] = 1, dp[1][1] = 1, dp[1][2] = 1로 초기화합니다.

점화식 구성

다음으로, 각 단계에서의 값들을 계산하는 규칙, 즉 점화식을 구성합니다. N번째 칸에 대해 생각해보면:

• 사자를 배치하지 않는 경우 (dp[N][0]): 이전 칸(N-1)에 사자가 어디에 배치되었든 상관없으므로 dp[N-1][0], dp[N-1][1], dp[N-1][2]의 합입니다.
• 사자를 첫 번째 칸에만 배치하는 경우 (dp[N][1]): 이전 칸에 사자가 첫 번째 칸이나 배치되지 않았어야 하므로 dp[N-1][0]과 dp[N-1][2]의 합입니다.
• 사자를 두 번째 칸에만 배치하는 경우 (dp[N][2]): 이전 칸에 사자가 두 번째 칸이나 배치되지 않았어야 하므로 dp[N-1][0]과 dp[N-1][1]의 합입니다.

결과 계산

모든 칸에 대해 계산을 마치고 나면, 최종적으로 N번째 칸에 대해 세 가지 경우의 수를 모두 더하면 됩니다. 이 때, 문제에서 주어진 대로 9901로 나눈 나머지를 취합니다.

코드 구현

위의 단계들을 코드로 구현하면, 초기화 부분과 점화식을 반복문으로 계산하는 부분, 그리고 최종 결과를 출력하는 부분으로 나누어집니다.

#전체 코드

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

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

    vector<vector<int>> dp (N+1, vector<int> (3,0));
    dp[1][0] = 1;
    dp[1][1] = 1;
    dp[1][2] = 1;

    for (int i = 2; i <= N; i++) {
        dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 9901;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901;
    }

    int result = (dp[N][0] + dp[N][1] + dp[N][2]) % 9901;

    cout << result <<'\n';

    return 0;
}

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/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/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 탐색을 사용하여 모든 토마토가 익게 되는 최소 일수를 효율적으로 찾습니다.

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

#문제 간단 정리

체스판 위에서 나이트가 이동하는 최소 횟수를 계산하는 문제를 해결하기 위한 코드입니다. 코드는 입력으로 주어지는 테스트 케이스를 처리하고, 각 테스트 케이스에 대해 나이트가 최소 몇 번 움직여야 하는지를 출력합니다. 코드는 너비 우선 탐색(BFS)을 사용하여 문제를 해결합니다

#전체 코드

#include <iostream>
#include <queue>

using namespace std;

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

struct point {
	int x, y;
};

int main() {


	int N; cin >> N;
	while (N--) {
		int I;
		cin >> I;
		point now, target;
		cin >> now.x >> now.y >> target.x >> target.y;

		if (now.x == target.x && now.y == target.y) {
			cout << '0' << endl;
			continue;
		}

		int chessBoard[300][300] = { 0, };

		queue<point> q;
		q.push(now);
		chessBoard[q.front().x][q.front().y] = 0;

		while (!q.empty()) {
			int x = q.front().x;
			int y = q.front().y;
			q.pop();
			for (int i = 0; i < 8; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (0 <= nx && nx < I && 0 <= ny && ny < I) {
					if (chessBoard[nx][ny] == 0) {
						q.push({ nx,ny });
						chessBoard[nx][ny] = chessBoard[x][y] + 1;
					}
				}

			}
		}

		cout << chessBoard[target.x][target.y]<< endl;

		
	}






	return 0;
}

#문제 해결 방법

해당 문제는 나이트의 이동을 최소한의 움직임으로 목표 위치까지 가는 최단 거리를 찾는 문제입니다. 이를 위해 BFS(Breadth-First Search)를 사용합니다.

문제 해설:

1. 나이트의 이동
   나이트는 8가지 방향으로 움직일 수 있습니다. 문제에서 제시한 그림을 참고하면, 나이트의 모든 움직임을 (dx, dy)의 형태로 나타낼 수 있습니다.
2. BFS
   BFS는 시작 지점부터 가장 가까운 지점들부터 차례대로 탐색하는 알고리즘입니다. 체스판에서의 나이트 이동도 이 알고리즘으로 효율적으로 해결할 수 있습니다. BFS를 사용하면, 각 칸에 도달하는 데 필요한 최소한의 움직임 횟수를 찾을 수 있습니다.

코드 설명:

• 변수
  • dx, dy: 나이트의 이동 방향을 저장한 배열입니다.
  • point: x, y 좌표를 갖는 구조체입니다.
  • chessBoard: 각 위치에 도달하기 위한 최소 움직임 횟수를 저장하는 체스판입니다.
• 프로세스
  1. 테스트 케이스의 수를 입력 받습니다.
  2. 각 테스트 케이스마다
     • 체스판의 크기, 시작 위치, 목표 위치를 입력 받습니다.
     • 시작 위치와 목표 위치가 같다면, 움직일 필요가 없으므로 0을 출력하고 다음 테스트 케이스로 넘어갑니다.
     • 그렇지 않다면, BFS로 최단 거리를 찾습니다.
     • BFS를 진행하며, 체스판에 각 칸까지 도달하기 위한 최소 움직임 횟수를 저장합니다.
     • 목표 위치까지의 최소 움직임 횟수를 출력합니다.

BFS를 사용하여 문제를 해결하면, 체스판의 각 칸까지 도달하는 데 필요한 최소 움직임 횟수를 효율적으로 찾을 수 있습니다.