점(.)과 숫자로 구성된 문자열이 하나 주어졌다고 가정해 보겠습니다. 점은 해당 셀이 비어 있음을 의미하고, 어떤 셀에 숫자 x가 적혀 있다면 그 셀에서 문자열 범위 안에서 왼쪽 또는 오른쪽으로 정확히 x칸 이동할 수 있습니다. 우리의 목표는 특정 셀을 두 번 이상(서로 다른 경로로) 방문할 수 있는지 확인하는 것입니다.
예를 들어 문자열이 ". 2 . . . 2 . ."와 같다면, 네 번째 셀은 두 가지 서로 다른 방법으로 도달할 수 있습니다. 두 번째 셀에서 오른쪽으로 두 칸 이동하거나, 여섯 번째 셀에서 왼쪽으로 두 칸 이동하면 됩니다. 따라서 이 경우 답은 "예"입니다.
접근 방식
이 문제는 각 셀에 도달할 수 있는 경로의 수를 세는 방식으로 해결할 수 있습니다.
먼저 문자열의 길이와 같은 크기의 visited[] 배열을 만들어 각 셀의 방문 가능 횟수를 기록합니다. 그다음 문자열을 처음부터 끝까지 순회하면서 다음과 같이 처리합니다.
- 현재 문자가 점(.)이라면 아무 작업도 수행하지 않습니다.
- 현재 문자가 숫자 x라면, 인덱스 i를 기준으로 [i − x, i + x] 범위에 속하는 모든 셀의 방문 횟수를 1씩 증가시킵니다. 단, 범위가 문자열의 양 끝을 벗어나지 않도록 경계를 조정해야 합니다.
순회가 끝난 후 visited 배열을 검사하여 방문 횟수가 2 이상인 셀이 하나라도 존재하면 해당 셀을 두 번 이상 방문할 수 있는 것이므로 true를 반환하고, 그렇지 않으면 false를 반환합니다.
예제 코드
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool canVisitCellTwice(string s) {
int n = s.size();
vector<int> visited(n, 0);
// 각 숫자 셀에서 도달 가능한 범위의 방문 횟수 증가
for (int i = 0; i < n; i++) {
if (s[i] == '.')
continue;
int x = s[i] - '0';
int left = max(0, i - x);
int right = min(n - 1, i + x);
for (int j = left; j <= right; j++)
visited[j]++;
}
// 두 번 이상 방문 가능한 셀이 있는지 확인
for (int i = 0; i < n; i++) {
if (visited[i] > 1)
return true;
}
return false;
}
int main() {
string s = ".2..2..";
if (canVisitCellTwice(s))
cout << "셀을 두 번 이상 방문할 수 있습니다";
else
cout << "두 번 이상 방문할 수 있는 셀이 없습니다";
}출력 결과
셀을 두 번 이상 방문할 수 있습니다
위 예제에서 인덱스 1의 숫자 2는 인덱스 0~3의 셀에 도달 가능하게 하고, 인덱스 5의 숫자 2는 인덱스 3~7의 셀에 도달 가능하게 합니다. 인덱스 3(네 번째 셀)은 두 숫자 모두로부터 도달할 수 있으므로 방문 횟수가 2가 되어 true가 반환됩니다.
복잡도 분석
문자열의 길이를 n이라 할 때, 각 숫자 셀마다 최대 2x+1개의 셀을 갱신하므로 시간 복잡도는 O(n·k)(k는 최대 이동 거리)입니다. 일반적인 경우 O(n²) 이내로 동작하며, 공간 복잡도는 방문 횟수를 저장하는 배열 때문에 O(n)입니다.