[백준] 던전지도 - 19543

문제 링크

19543번: 던전 지도

 

잘못된 접근

보스방에서부터 하단에 U, 좌측에 R 타일이 있다면 queue에 넣어 순서대로 살펴본다면 문제를 해결할 수 있습니다.

이를 BFS 알고리즘을 사용해 풀이를 진행해보았으나 시간 초과가 발생했습니다.

 

최악의 경우 40,000,000,000번(200,000 * 200,000)의 연산이 필요하기 때문입니다.

 

이에 아래와 같이 U 타일의 위치를 계산해두어 계산의 횟수를 줄여 보았으나 동일한 이유로 시간초과가 발생했습니다.

• 현재 위치의 타일이 R이라면 가장 가까운 U 타일의 위치를 기록한다.
• 현재 위치의 타일이 U라면 자신의 위치를 기록한다.
• 예) RRURRUU -> 2225556

풀이

모든 층은 아래 그림과 같은 형태를 가지고 있습니다.

 

이를 수식으로 표현해보면 다음과 같습니다.

• 위층의 끝 >= 아래층의 끝
• 위층의 시작 <= 아래층의 시작

위층과 맞닿아 있지 않다면 탑을 오를 수 없으므로 위층의 시작 지점부터 아래층의 끝지점까지만 연산을 진행하면 됩니다.

풀이 코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
  // freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n, m, k;
  cin >> n >> m >> k;
  string str;
  vector<string> mapStructure(k);
  getline(cin, str);
  for (int i = 0; i < k; i++)
  {
    getline(cin, mapStructure[i]);
  }
  getline(cin, str);
  long long ans = 0;
  int cur = str[n - 1] - 'A';
  int end = m - 1, start = m - 1;
  for (int i = m - 2; i >= 0; i--)
  {
    if (mapStructure[cur][i] == 'U')
    {
      start = i + 1;
      break;
    }
    if (i == 0)
      start = 0;
  }
  ans += end - start + 1;
  bool flag = false;
  for (int i = n - 2; i >= 0; i--)
  {
    cur = str[i] - 'A';
    for (; end >= 0; end--)
    {
      if (mapStructure[cur][end] == 'U')
      {
        break;
      }
      if (end == 0)
      {
        flag = true;
        break;
      }
    }
    if (flag)
      break;
    start--;
    for (; start >= 0; start--)
    {
      if (mapStructure[cur][start] == 'U')
      {
        start++;
        break;
      }
    }
    if (start < 0)
      start = 0;
    ans += end - start + 1;
  }
  cout << ans;
  return 0;
}