[프로그래머스] (C++) 방문길이

문제

• 링크

힌트

• 이미 간 곳에 대한 정보를 어떻게 저장해야 갈 수 있는 곳에 대한 정보를 쉽게 얻을 수 있을까?
• 어디에서 어느 방향으로 갔는지를 저장하면 되지 않을까?

소스 코드

// [프로그래머스] 방문 길이

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>

int solution (std::string dirs) {
        int answer{0};
        std::pair<int, int> lastPos, nextPos;
        std::vector<std::pair<int, int>> U, D, L, R;
        lastPos.first = 0;
        lastPos.second = 0;
        for (int i = 0; i < dirs.length(); i++) {
                if (dirs[i] == 'U') {
                        if (lastPos.second == 5) continue;
                        nextPos.first = lastPos.first;
                        nextPos.second = lastPos.second + 1;
                        if ((std::find(U.begin(), U.end(), lastPos) == U.end()) && (std::find(D.begin(), D.end(), nextPos) == D.end())) {
                                answer++;
                                U.push_back(lastPos);
                        }
                        lastPos = nextPos;
                } else if (dirs[i] == 'D') {
                        if (lastPos.second == -5) continue;
                        nextPos.first = lastPos.first;
                        nextPos.second = lastPos.second - 1;
                        if ((std::find(U.begin(), U.end(), nextPos) == U.end()) && (std::find(D.begin(), D.end(), lastPos) == D.end())) {
                                answer++;
                                D.push_back(lastPos);
                        }
                        lastPos = nextPos;
                } else if (dirs[i] == 'L') {
                        if (lastPos.first == -5) continue;
                        nextPos.first = lastPos.first - 1;
                        nextPos.second = lastPos.second;
                        if ((std::find(R.begin(), R.end(), nextPos) == R.end()) && (std::find(L.begin(), L.end(), lastPos) == L.end())) {
                                answer++;
                                L.push_back(lastPos);
                        }
                        lastPos = nextPos;
                } else {
                        if (lastPos.first == 5) continue;
                        nextPos.first = lastPos.first + 1;
                        nextPos.second = lastPos.second;
                        if ((std::find(R.begin(), R.end(), lastPos) == R.end()) && (std::find(L.begin(), L.end(), nextPos) == L.end())) {
                                answer++;
                                R.push_back(lastPos);
                        }
                        lastPos = nextPos;
                }
        }
        return answer;
}

해설

어느 점에서 어느 방향으로 갔는지를 기록한다. 이때, 해당 방향으로 벡터를 만들어 해당 위치 (X,Y)를 벡터에 집어 넣는다. 이미 지났던 길임을 판별하기 위해 가야될 방향 벡터에 현재 위치가 있는지를 보거나, 반대로 반대 방향에서 현재 위치로 올 때 이미 지났던 길은 아닌지 확인한다.

1. direction 판별 (U인지 D인지 L인지 R인지)
2. edge-case 판별 (U: y가 5이면 무시, D: y가 -5이면 무시, L: x가 -5이면 무시, R: x가 5이면 무시)
3. availability 판별: 예). 주어진 direction이 D이면 D벡터에서에서 해당 posX, posY가 있는지 확인! 없으면 answer++. 그 외, D이면 UP벡터에서 (posX, posY-1)이 있는지 확인! (반대 방향에서 이미 지났을 수 있으니까)
4. push back으로 pair(posX, posY) 를 받은 dir의 벡터에 넣자