(프로그래머스 c++)방문 길이

문제 설명

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

• U: 위쪽으로 한 칸 가기

• D: 아래쪽으로 한 칸 가기

• R: 오른쪽으로 한 칸 가기

• L: 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.

예를 들어, ULURRDLLU로 명령했다면

• 1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다.

• 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다.

이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다. (8, 9번 명령어에서 움직인 길은 2, 3번 명령어에서 이미 거쳐 간 길입니다)

단, 좌표평면의 경계를 넘어가는 명령어는 무시합니다.

예를 들어, LULLLLLLU로 명령했다면

• 1번 명령어부터 6번 명령어대로 움직인 후, 7, 8번 명령어는 무시합니다. 다시 9번 명령어대로 움직입니다.

이때 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다.

명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요.

 

-----------------------------------------------

multimap을 이용하여 해결.

우선 그래프에서 해당 좌표의 방문 여부를 알기 위해 bool형 visited[11][11]을 선언하고,

(5, 5)를 시작점으로 삼고, true로 만들어준다.

그리고 길이를 알기 위해 multimap을 선언.

multimap<x좌표, pair<y좌표, pair<이동 전 x좌표, 이동 전 y좌표>>> 식으로 mm을 선언한다.

 

for문을 이용해 좌표를 움직인다.

tmpX는 이동하기 전 x좌표, tmpY는 이동하기 전 y좌표를 나타낸다.

키워드에 따라 x, y좌표를 움직이고, 해당 좌표들이 좌표평면을 벗어나면 tmpX, tmpY로 변경하여

움직이지 않도록 한다.

 

만약 visitied[x][y] == false라면 한번도 방문하지 않은 좌표이므로 answer++을 해주고

지나왔던 길로 표시하기 위해 mm에 넣어주도록 한다.

여기서 x, y로 이동한 길은 tmpX, tmpY로 이동할 때의 길과 같으므로

두개의 길 모두 mm에 넣어주도록 한다.

 

만약 visited[x][y] == true라면 방문했다는 것을 나타낸다.

여기서 어느 좌표에서 왔는지, 해당 좌표에서 온 길이 지나왔던 길인지 확인한다.

x, y에서 tmpX, tmpY로 왔던 길과

tmpX, tmpY에서 x, y로 왔던 길을 for문으로 각각 확인하도록 하고,

오지 않았던 길이라면 answer++을 해주고, mm에 각각 넣어주도록 하면 된다.

 

#include <string>
#include <iostream>
#include <map>

using namespace std;

int solution(string dirs) {
    int answer = 0;
    bool visited[11][11] = {false, };
    int x = 5, y = 5;
    multimap<int, pair<int, pair<int, int>>> mm;
    
    visited[5][5] = true;
    
    for(int i = 0; i < dirs.size(); i++)
    {
        int tmpX = x, tmpY = y;
        
        if(dirs[i] == 'U')
            y++;
        else if(dirs[i] == 'D')
            y--;
        else if(dirs[i] == 'L')
            x--;
        else if(dirs[i] == 'R')
            x++;
        
        if(x < 0 || x > 10 || y < 0 || y > 10)
        {
            x = tmpX;
            y = tmpY;
            continue;
        }
        
        if(visited[x][y] == false)
        {
            visited[x][y] = true;
            answer++;
            mm.insert(make_pair(x, make_pair(y, make_pair(tmpX, tmpY))));
            mm.insert(make_pair(tmpX, make_pair(tmpY, make_pair(x, y))));
        }
        else
        {
            bool check = false;
            auto find_key = mm.find(x);
            for(auto itr = mm.lower_bound(find_key->first); itr != mm.upper_bound(find_key->first); itr++)
            {
                if(itr->second.first == y && itr->second.second.first == tmpX && itr->second.second.second == tmpY)
                {
                    check = true;
                    break;
                }
            }
            
            if(!check)
            {
                check = false;
                auto find_key = mm.find(tmpX);
                for(auto itr = mm.lower_bound(find_key->first); itr != mm.upper_bound(find_key->first); itr++)
                {
                    if(itr->second.first == tmpY && itr->second.second.first == x && itr->second.second.second == y)
                    {
                        check = true;
                        break;
                    }
                }
                if(!check)
                {
                    answer++;
                    mm.insert(make_pair(x, make_pair(y, make_pair(tmpX, tmpY))));
                    mm.insert(make_pair(tmpX, make_pair(tmpY, make_pair(x, y))));
                }
            }   
        }
    }
    return answer;
}