프로그래머스 [연습문제 / 방문 길이](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 49994 방문 길이

---

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49994

문제 설명:

게임 캐릭터가 좌표평면 (0, 0)에서 시작하여 U(위), D(아래), R(오른쪽), L(왼쪽) 명령어로 이동합니다. 좌표평면의 경계는 -5부터 5까지이며, 경계를 넘어가는 명령어는 무시됩니다. 이때 캐릭터가 처음 걸어본 길의 길이를 구하는 문제입니다. 중요한 점은 (0,0)에서 (0,1)로 가는 길과 (0,1)에서 (0,0)으로 가는 길은 같은 길로 간주된다는 것입니다.

---

문제 해결 코드

#include <string>
#include <set>
using namespace std;

int solution(string dirs) {
    // 처음 걸어본 간선(길)을 저장하는 집합
    set<pair<pair<int,int>, pair<int,int>>> visitedPaths;
    
    // 현재 좌표 (0, 0)에서 시작
    int x = 0, y = 0;
    
    // 각 명령어 처리
    for (char cmd : dirs) {
        int nextX = x, nextY = y;
        
        // 명령어에 따른 다음 좌표 계산
        if (cmd == 'U') {
            nextY++;
        } else if (cmd == 'D') {
            nextY--;
        } else if (cmd == 'R') {
            nextX++;
        } else if (cmd == 'L') {
            nextX--;
        }
        
        // 경계 체크: -5 ~ 5 범위를 벗어나면 무시
        if (nextX < -5 || nextX > 5 || nextY < -5 || nextY > 5) {
            continue;
        }
        
        // 간선을 정규화: 항상 작은 좌표가 먼저 오도록
        pair<int,int> from = {x, y};
        pair<int,int> to = {nextX, nextY};
        
        // 좌표 정렬 (양방향을 하나의 간선으로 처리)
        if (from > to) {
            swap(from, to);
        }
        
        // 간선을 집합에 추가 (중복은 자동으로 제거됨)
        visitedPaths.insert({from, to});
        
        // 현재 위치 갱신
        x = nextX;
        y = nextY;
    }
    
    // 처음 걸어본 길의 개수 반환
    return visitedPaths.size();
}

---

코드 설명

• 핵심 알고리즘: 집합(set) 자료구조를 활용한 간선 관리입니다. 각 이동을 간선으로 표현하고, 양방향 간선을 하나의 간선으로 정규화하여 저장합니다. (0,0)→(0,1)과 (0,1)→(0,0)을 동일한 간선으로 처리하기 위해 두 좌표를 정렬하여 항상 작은 좌표가 먼저 오도록 합니다.
• 구현 세부사항:
  • set 자료구조를 사용하여 중복 간선을 자동으로 제거합니다.
  • 각 명령어에 대해 다음 좌표를 계산하고 경계 검사를 수행합니다.
  • from과 to 좌표를 비교하여 작은 좌표가 앞에 오도록 정렬합니다 (swap 활용).
  • 정규화된 간선을 set에 삽입하여 방문 기록을 관리합니다.
  • 원본 코드의 두 개 map (mpx, mpy)을 하나의 set으로 통합하여 구조를 간소화했습니다.
• 시간/공간 복잡도: 시간 복잡도는 O(n log m)입니다. n은 명령어 길이(최대 500), m은 저장된 간선 수(최대 121)로 set 삽입 연산이 O(log m)입니다. 공간 복잡도는 O(m)으로 최대 121개의 간선을 저장할 수 있습니다 (11×11 좌표평면의 간선 수).

---

실행 예시

입력:

dirs = "ULURRDLLU"

실행 과정:

• U: (0,0) → (0,1), 간선 [(0,0), (0,1)] 추가 (개수: 1)
• L: (0,1) → (-1,1), 간선 [(-1,1), (0,1)] 추가 (개수: 2)
• U: (-1,1) → (-1,2), 간선 [(-1,1), (-1,2)] 추가 (개수: 3)
• R: (-1,2) → (0,2), 간선 [(-1,2), (0,2)] 추가 (개수: 4)
• R: (0,2) → (1,2), 간선 [(0,2), (1,2)] 추가 (개수: 5)
• D: (1,2) → (1,1), 간선 [(1,1), (1,2)] 추가 (개수: 6)
• L: (1,1) → (0,1), 간선 [(0,1), (1,1)] 추가 (개수: 7)
• L: (0,1) → (-1,1), 간선 [(-1,1), (0,1)] 중복 (개수: 7)
• U: (-1,1) → (-1,2), 간선 [(-1,1), (-1,2)] 중복 (개수: 7)

출력:

7

---

결과

간선을 정규화하여 양방향 이동을 하나의 길로 처리하는 것이 핵심입니다. 원본 코드의 복잡한 map 구조를 하나의 set으로 통합하여 코드 가독성과 효율성을 높였습니다. 좌표 정렬을 통해 양방향 간선 처리 로직을 단순화했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!