[Programmers] 방문길이 c++ (pair, map)

 

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

 

✔ 문제 이해

캐릭터의 움직임이 좌표평면 직선 상에서 주어졌을때, 처음 방문하는 직선의 수를 구하여라.

 

✔ 풀이 + 코드

map을 이용하여 key로 방문한 좌표를, value로 방문한 적이 있는지 없는지를 판별했다. 하지만 직선의 방문을 처리해야 했기 때문에 key 부분에 {이전좌표, 다음좌표}의 쌍으로 넣어주었다. 그리고 (0,0)에서 (0,1)로 간것과 (0,1)에서 (0,0)으로 간 것은 같은 직선이기 때문에 map에 방문한 이력을 넣어줄 때 반대방향으로도 넣어주었다.

 

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

int solution(string dirs) {
    int answer = 0;
    // (x, y)좌표 두 개의 간선과 그 간선의 등장횟수를 저장할 map
    map<pair<pair<int, int>, pair<int,int>>, bool> mp;
    
    int curX = 0;
    int curY = 0;
    for(auto edge : dirs){
        int startX = curX;
        int startY = curY;
        
        if(edge == 'U'){
            if(curY + 1 > 5) continue;
            curY += 1;
        }
        else if(edge == 'D'){
            if(curY - 1 < -5) continue;
            curY -= 1;
        }
        else if(edge == 'R'){
            if(curX + 1 > 5) continue;
            curX += 1;
        }
        else if(edge == 'L'){
            if(curX - 1 < -5) continue;
            curX -= 1;
        }
        
        if(mp[{{startX, startY},{curX, curY}}] == true) continue;
        
        mp[{{startX, startY},{curX, curY}}] = true;
        mp[{{curX, curY},{startX, startY}}] = true;
        answer++;
    }
    return answer;
}

 

✔ 피드백

• pair를 야무지게 써볼 수 있었다.
• -5~5 사이의 숫자가 아닌 경우에는 바로 continue를 해줘야 한다. 그렇지 않으면 머물러있는 좌표도 map에 저장된다.
• 생각하기 어려웠던 문제인 것 같은데 바로 map을 생각할 수 있어서 뿌듯했지만 구현에 있어서는 아직도 시간이 좀 걸리는 것 같다.

✔ reference

https://ansohxxn.github.io/programmers/104/