메뚜기가 목표 지점에 도달할 수 있는지 확인하는 C++ 코드

크기가 n인 문자열 S와 하나의 숫자 k가 주어져 있다고 가정해 보겠습니다. 문자열은 네 가지 종류의 문자로 구성되어 있으며, 메뚜기가 점프하여 목표 지점에 도달하려고 합니다. 각 문자의 의미는 다음과 같습니다.

문자 '.'는 해당 칸이 비어 있음을 의미하고, 문자 '#'는 해당 칸에 장애물이 있어 메뚜기가 그곳으로 점프할 수 없음을 의미합니다. 'G'는 메뚜기가 시작되는 위치를 나타내며, 'T'는 목표 칸을 나타냅니다. 메뚜기는 현재 위치에서 정확히 k칸 떨어진 곳으로만 점프할 수 있습니다. 따라서 우리는 메뚜기가 목표 지점까지 점프할 수 있는지 여부를 확인해야 합니다.

예를 들어, 입력이 S = "#G#T#"; k = 2라고 한다면 출력은 True가 됩니다. G에서 T까지의 거리가 2칸이고 k가 2이므로 메뚜기는 단 한 번의 점프로 목표에 도달할 수 있기 때문입니다.

풀이 단계

이 문제를 해결하기 위해 다음 단계를 따릅니다 −

n := size of S
x := position of 'G' in S
y := position of 'T' in S
if x > y, then:
    swap x and y
for initialize i := x, when i < y, update i := i + k, do:
    if S[i] is same as '#', then:
        Come out from the loop
if i is same as y, then:
    return true
Otherwise
    return false

핵심 아이디어는 'G'와 'T'의 위치를 찾은 후, 항상 왼쪽 위치에서 오른쪽 위치 방향으로 k칸씩 이동하면서 경로상에 장애물('#')이 있는지 검사하는 것입니다. 중간에 장애물을 만나면 반복문을 빠져나오고, 정확히 'T' 위치에 도달했을 때만 true를 반환합니다.

예시 코드

더 나은 이해를 위해 다음 구현 예시를 살펴보겠습니다 −

#include <bits/stdc++.h>
using namespace std;
bool solve(string S, int k)
{
    int n = S.size();
    int i;
    int x = S.find('G');
    int y = S.find('T');
    if (x > y)
        swap(x, y);
    for (i = x; i < y; i += k)
    {
        if (S[i] == '#')
            break;
    }
    if (i == y)
        return true;
    else
        return false;
}
int main()
{
    string S = "#G#T#";
    int k = 2;
    cout << solve(S, k) << endl;
}

입력

"#G#T#", 2

출력

1