[프로그래머스] [Summer/Winter Coding(~2018)] 주식가격(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "방문 길이" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제는 게임 캐릭터가 주어진 명령어('U', 'D', 'R', 'L')에 따라 움직일 때, 캐릭터가 처음 걸어본 길의 총 길이를 계산하는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크 : 

https://school.programmers.co.kr/learn/courses/30/lessons/49994

프로그래머스

문제 개요

"방문 길이" 문제는 게임 캐릭터가 주어진 명령어('U', 'D', 'R', 'L')에 따라 움직일 때, 캐릭터가 처음 걸어본 길의 총 길이를 계산하는 문제입니다. 좌표 평면의 경계를 넘어서는 명령어는 무시되며, 이미 방문한 길은 길이 계산에 포함되지 않습니다.

해결 방법

이 문제는 좌표 평면 위의 경로를 추적하고, 캐릭터가 처음 방문한 길만을 카운트하는 방식으로 해결할 수 있습니다. 이를 위해 4차원 배열을 사용하여 각 좌표 간의 방문 여부를 저장합니다.

코드 구현

#include <string>
#include <bits/stdc++.h>
using namespace std;

bool visited[12][12][12][12]; // 각 좌표 간의 방문 여부를 저장하는 4차원 배열

// 현재 위치와 이동 명령을 바탕으로 새로운 위치를 반환하는 함수
pair<int,int> GetPos(int y,int x,char input){
    switch(input){
        case 'U': // 위로 이동
            return {y + 1,x};
        case 'D': // 아래로 이동
            return {y - 1,x};
        case 'R': // 오른쪽으로 이동
            return {y,x + 1};
        case 'L': // 왼쪽으로 이동
            return {y,x- 1};
    }
    return {0,0};
}

// 특정 경로가 이미 방문되었는지 확인하는 함수
bool Visited(int cy,int cx,int ny,int nx){
    return visited[cy][cx][ny][nx];
}

// 주어진 명령어에 따라 이동하며 처음 방문한 길의 길이를 계산하는 함수
int solution(string dirs) {
    int answer = 0;
    int curY = 5; // 초기 Y 좌표
    int curX = 5; // 초기 X 좌표
    
    for(int i = 0; i < dirs.size(); i++)
    {
        pair<int,int> newpos = GetPos(curY,curX,dirs[i]);
        // 좌표 평면의 경계를 넘어서는 경우 무시
        if(newpos.first < 0 || newpos.first > 10 || newpos.second < 0 || newpos.second > 10)
            continue;
        // 처음 방문하는 경로인 경우 카운트 증가
        if(Visited(curY,curX,newpos.first,newpos.second) == false){
            visited[curY][curX][newpos.first][newpos.second] = true;
            visited[newpos.first][newpos.second][curY][curX] = true;
            answer++;
        }
        // 현재 위치 업데이트
        curY = newpos.first;
        curX = newpos.second;
    }
    
    return answer;
}

코드 설명

이 코드는 주어진 문자열 dirs에서 각 문자를 명령어로 해석하여 캐릭터를 이동시킵니다. 캐릭터의 이동 경로는 4차원 배열 visited를 통해 추적되며, 처음 방문하는 경로일 때만 길이(answer)를 증가시킵니다. 이 방법은 좌표 평면의 경계를 고려하며, 이미 방문한 경로는 재방문 시 길이 계산에 포함되지 않습니다.

결론

"방문 길이" 문제는 좌표 평면과 경로 추적 알고리즘을 활용하여 해결할 수 있습니다. 이 문제는 좌표 평면 상의 경로를 효과적으로 관리하고, 중복된 경로를 피하는 방법에 대한 이해를 요구합니다. 이러한 접근 방식은 다양한 경로 추적 및 좌표 기반 문제에 적용될 수 있습니다.