C++로 주어진 방향대로 이동한 후 시작 위치 (0, 0)으로 돌아올 수 있는지 확인하는 방법

문제 개요

어떤 사람이 좌표 평면의 원점, 즉 (0, 0) 위치에 서 있다고 가정해 보겠습니다. 이동 경로는 네 개의 문자로 구성된 문자열로 주어지며, 각 문자는 다음 방향을 의미합니다.

• E: 동쪽(east)
• W: 서쪽(west)
• N: 북쪽(north)
• S: 남쪽(south)

이 문제의 목표는 문자열에 담긴 모든 이동을 순서대로 수행한 뒤, 다시 시작점인 (0, 0)으로 돌아올 수 있는지 판별하는 것입니다.

예를 들어 입력이 "EENWWS"라면 결과는 참(true)이 됩니다. 동쪽으로 두 칸 이동한 뒤 북쪽으로 한 칸, 서쪽으로 두 칸, 마지막으로 남쪽으로 한 칸 이동하면 결국 처음 위치로 되돌아오기 때문입니다.

접근 방법

핵심 아이디어는 매우 간단합니다. 동쪽과 서쪽 이동은 서로 상쇄되고, 북쪽과 남쪽 이동 역시 서로 상쇄됩니다. 따라서 각 축의 이동량을 누적하여 두 값이 모두 0으로 끝나는지만 확인하면 됩니다.

1. 이동 문자열의 길이를 l이라고 합니다.
2. l이 0이면 이동 자체가 없으므로 true를 반환합니다.
3. 가로축 누적값 lft와 세로축 누적값 up을 0으로 초기화합니다.
4. 문자열을 처음부터 끝까지 순회하며 다음과 같이 값을 갱신합니다.
   • 'W'이면 lft를 1 증가
   • 'E'이면 lft를 1 감소
   • 'N'이면 up을 1 증가
   • 'S'이면 up을 1 감소
5. 순회가 끝난 후 lft와 up이 모두 0이면 true, 그렇지 않으면 false를 반환합니다.

이 알고리즘의 시간 복잡도는 문자열 길이에 비례하는 O(n)이며, 추가 공간 없이 두 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다.

C++ 구현 예제

아래 코드를 통해 실제 구현 과정을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool solve(string moves) {
      int l = moves.length();
      if (l == 0) {
         return true;
      }
      int lft = 0, up = 0;
      for (int i = 0; i < l; i++) {
         if (moves[i] == 'W') {
            lft++;
         }
         if (moves[i] == 'E') {
            lft--;
         }
         if (moves[i] == 'N') {
            up++;
         }
         if (moves[i] == 'S') {
            up--;
         }
      }
      if (lft == 0 && up == 0) {
         return true;
      }
      return false;
   }
};
int main() {
   Solution ob;
   cout << (ob.solve("EENWWS"));
   return 0;
}

입력

"EENWWS"

출력

1

출력값 1은 불리언 값 true를 의미하며, "EENWWS" 경로로 이동하면 정확히 시작 위치인 (0, 0)으로 돌아올 수 있음을 나타냅니다.