프로그래머스 레벨2 <방문 길이> C++ 풀이

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

프로그래머스

이런 그래프 탐색류의 문제들 중에 제 기준에서는 처음 보는 유형의 문제였습니다.

정점이 아니라 정점과 정점 사이의 길에 대한 중복체크라는 새로운 해결요소를 내놓은 문제라 시간 꽤나 잡아먹은 것 같습니다. 그래도 혼자 힘으로 풀어낼 수 있었어서 굉장히 뿌듯하고 만족스럽습니다. 구조체의 힘에 대해서 다시 한번 깨닫게 된 계기였습니다.

 

문제의 내용은 결국 입력으로 주어진 방향에 맞추어 좌표평면에서 움직이는데, 그 경로 중 중복되는 경로는 제외하고 총 이동거리를 구하는 문제였습니다. 처음에는 별 생각없이 출발위치 & 이동할 위치 둘의 좌표값의 방문여부를 확인해서 방문 한 곳은 제외하도록 코드를 짜봤는데 오답이었습니다. 

 

무엇이 문젠가 했더니, 이미 방문한 곳에서 다시 방문한 곳으로 이동하는 경우중에 그 이동하는 길은 중복이 아닌 경우가 존재합니다. 예를들면 (0,0)에서 (1,0)으로 이동하고 두 점 방문체크. (1,0)에서 (1,1)로 이동하고 (1,1) 방문체크. (1,1)에서 (0,1)로 이동하고 (0,1) 방문체크. 여기서 중요합니다. (0,1)에서 (0,0)으로 이동할때 (0,0)은 이미 방문 체크가 되어있어 위 코드에서는 경로로 체크하지 않지만, 사실 (0,1)에서 (0,0)으로 이동하는 경로는 한번도 이동한적이 없기 때문에 포함시켜줘야 하는 것입니다. 이로써 위 코드가 잘못되었다는 것을 인지했고, 경로에대한 체크가 필요하겠다고 생각했습니다.

 

이런 저런 아이디어를 떠올려봤는데, 결국 경로를 체크하기엔 각 좌표에 대해 구조체를 사용하는거 말고는 떠오르지가 않았습니다. Node라는 구조체에 위,아래,왼쪽,오른쪽에 대한 방문여부를 bool값으로 주고 (0,0)에서 (0,1)로 이동한다면 (0,0)좌표의 Node구조체에 위방향 변수 true로 변경. 그리고 (0,1)좌표 구조체의 아래방향 변수 true로 변경. 이렇게하면 그 이동한 경로에 대한 중복 체크가 되기 때문에 문제에서 답을 구할 수 있을거라 생각했습니다. 그리고 깔끔하게 정답을 받았습니다! (추가로 음수 좌표에 대해서 배열로 표현할수가 없기 때문에 실제 좌표평면의 (0,0)이 visited배열의 [5][5]가 되도록 조정이 필요합니다)

 

 

#include <string>
using namespace std;
 
struct Node
{
    bool u;
    bool d;
    bool l;
    bool r;
    Node()
    {
        u = false;
        d = false;
        l = false;
        r = false;
    }
};
 
Node visited[11][11];
 
int solution(string dirs) {
    int answer = 0;
    int x = 0;
    int y = 0;
    int cur = 0;
 
    while (cur < dirs.length())
    {
        if (dirs[cur] == 'U')
        {
            cur++;
            int tmpX = x;
            int tmpY = y + 1;
            if (tmpX > 5 || tmpX < -5 || tmpY > 5 || tmpY < -5)
                continue;
            if (visited[x + 5][y + 5].u == true)
            {
                x = tmpX;
                y = tmpY;
                continue;
            }
            visited[x+5][y+5].u = true;
            visited[tmpX+5][tmpY+5].d = true;
            x = tmpX;
            y = tmpY;
            answer++;
        }
        else if (dirs[cur] == 'D')
        {
            cur++;
            int tmpX = x;
            int tmpY = y - 1;
            if (tmpX > 5 || tmpX < -5 || tmpY > 5 || tmpY < -5)
                continue;
            if (visited[x + 5][y + 5].d == true)
            {
                x = tmpX;
                y = tmpY;
                continue;
            }
            
            visited[x + 5][y + 5].d = true;
            visited[tmpX+5][tmpY+5].u = true;
            x = tmpX;
            y = tmpY;
            answer++;
        }
        else if (dirs[cur] == 'L')
        {
            cur++;
            int tmpX = x - 1;
            int tmpY = y;
            if (tmpX > 5 || tmpX < -5 || tmpY > 5 || tmpY < -5)
                continue;
            if (visited[x + 5][y + 5].l == true)
            {
                x = tmpX;
                y = tmpY;
                continue;
            }
            
            visited[x + 5][y + 5].l = true;
            visited[tmpX+5][tmpY+5].r = true;
            x = tmpX;
            y = tmpY;
            answer++;
        }
        else // 'R'
        {
            cur++;
            int tmpX = x + 1;
            int tmpY = y;
            if (tmpX > 5 || tmpX < -5 || tmpY > 5 || tmpY < -5)
                continue;
            if (visited[x + 5][y + 5].r == true)
            {
                x = tmpX;
                y = tmpY;
                continue;
            }
            
            visited[x + 5][y + 5].r = true;
            visited[tmpX+5][tmpY+5].l = true;
            x = tmpX;
            y = tmpY;
            answer++;
        }
    }
 
    return answer;
}