[C++로 풀이] 방문 길이 (그래프 간선 방문 체크)⭐⭐⭐

📌 방문 길이

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이

• 방문 체크를 하여 방문했던 곳이면 answer를 증가시키지 않는다.
• 5 X 5 크기의 좌표를 넘어서는 공간은 무시한다.

✈ 1차 풀이 ❌ (“정점”으로 방문 체크)

#include <string>
using namespace std;

int solution(string dirs) {
    int answer = 0;
    
    bool visited[11][11] = { false };
    
    // 출발 정점은 문제에선 (0, 0)긴한데 각 좌표를 배열로 다루기 위해 (5, 5)로 치환함. 좌상단이 배열 인덱스로 [0][0]가 되게끔 하기 위하여.
    int curX = 5;
    int curY = 5;
    visited[curX][curY] = true; // 출발지는 미리 방문 체크
    
    for(int i = 0; i < dirs.length(); ++i){
        int startX = curX; // 현재 간선에서의 출발 정점 X좌표
        int startY = curY; // 현재 간선에서의 출발 정점 Y좌표
        
        /* 이동 */
        if (dirs[i] == 'U'){
            if (curX - 1 < 0) // 무시
                continue;
            curX--;
        }
        if (dirs[i] == 'D'){
            if (curX + 1 > 10) // 무시
                continue;
            curX++;
        }
        if (dirs[i] == 'L'){
            if (curY - 1 < 0) // 무시
                continue;
            curY--;
        }
        if (dirs[i] == 'R'){
            if (curY + 1 > 10) // 무시
                continue;
            curY++;
        }
        
        if (visited[startX][startY] == true && visited[curX][curY] == true) // 출발정점, 도착정점 둘 다 방문한적 있다면 무시 
            continue;
        
        visited[curX][curY] = true; // 방문 체크
        answer++; // answer 증가
    }
    
    return answer;
}

처음엔 이렇게 방문한 좌표, 즉 “정점”을 기준으로 방문 체크를 했었다. 간선 하나의 출발 좌표와 도착 좌표 둘 다 방문했던 곳이면 방문한적이 있는 것으로 체크하도록 했었다. 근데 이렇게 하면 틀린다. ㅠ ㅜ 이렇게 정점으로 방문 체크를 하면 예제 1번에서 (7)번의 경우 answer가 증가 되지 않는다. 7번의 출발 좌표는 6번 에서, 7번의 도착 좌표는 1번에서 방문 했었기 때문이다.

따라서 "간선" 그 자체를 기준으로 방문 체크를 해야 한다.

✈ 2차 풀이 ⭕ (“간선”으로 방문 체크)

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

int solution(string dirs) {
    int answer = 0;
    map<pair<pair<int, int>, pair<int, int>>, bool> visitedEdge;

    int curX = 5;
    int curY = 5;
    for (int i = 0; i < dirs.length(); ++i) {
        int startX = curX;
        int startY = curY;

        if (dirs[i] == 'U') {
            if (curX - 1 < 0)
                continue;
            curX--;
        }
        if (dirs[i] == 'D') {
            if (curX + 1 > 10)
                continue;
            curX++;
        }
        if (dirs[i] == 'L') {
            if (curY - 1 < 0)
                continue;
            curY--;
        }
        if (dirs[i] == 'R') {
            if (curY + 1 > 10)
                continue;
            curY++;
        }

        if (visitedEdge[make_pair(make_pair(startX, startY), make_pair(curX, curY))] == true)
            continue;

        visitedEdge[make_pair(make_pair(startX, startY), make_pair(curX, curY))] = true;
        visitedEdge[make_pair(make_pair(curX, curY), make_pair(startX, startY))] = true;
        answer++;
    }
    
    return answer;
}

map<pair<pair<int, int>, pair<int, int>>, bool> visitedEdge;

[ (출발 정점 좌표),(도착 정점 좌표) ] (👉간선)를 Key 로 하고 방문한적 있는지 없는지를 value로 저장하는 visitedEdge map 을 사용했다.

• 성공적으로 방문 하기로 결정한 간선이라면
  • [ (출발 정점 좌표),(도착 정점 좌표) ] 도 방문 체크 해주고
  • [ (도착 정점 좌표),(출발 정점 좌표) ] 도 방문 체크 해줘야 한다. 둘 다 하나의 간선을 나타내는 것이나 마찬가지기 때문에.. (간선 그 자체를 방문 체크하는거라 방향 상관 없음)

나는 이렇게 두 개의 pair를 또 묶어준 pair 를 Key 로 가지는 map 을 사용했지만 4차원 배열 로 간선 방문 체크를 해도 괜찮았을 것 같다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기