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

문제 링크

코딩테스트 연습 - 방문 길이

 

 

 

풀이

범위 검사, 방문 이력 검사 함수와 x, y는 row, column으로 대조하여 풀었다.

 

// Node 구조체

row, column의 int 타입을 가지며 1)생성자와 2)복사 생성자, 3)비교 연산자 오버로딩, 4)대입 연산자 오버로딩을 정의하여 다른 외부에서 편하게 사용하였다.(참고로 Java에서는 this가 참조자고 C++에서는 this가 포인터라는 것을 일깨워줌)

 

// check_range 함수

범위 체크 함수.

size를 받아 범위를 초과하는지 체크한다.

 

// check_visit 함수

방문 이력 체크 함수.

tuple을 모아놓은 vector 컨테이너를 방문 이력으로 참조자를 사용하여 갱신(push_back)되도록 한다.

 

// solution 함수

주어진 방향 string을 돌면서

Up은 row--;

Down은 row++;

Left는 col--;

right는 coll++;

을 하면서 1) 범위체크, 2) 방문이력 체크를 한다.

방문 이력이 없으면 answer++; 해주면서 진행한다.

 

 

#include <string>
#include <vector>
#include <tuple>

using namespace std;

typedef struct Node{
    int r, c;
    Node(int _r, int _c){       // 생성자
        r = _r;
        c = _c;
    }
    Node(Node& node){           // 복사 생성자
        r = node.r;
        c = node.c;
    }
    bool operator ==(Node& node){        // 비교 연산자 오버로딩
        if(this->r != node.r) return false;
        if(this->c != node.c) return false;
        return true;
    }
    void operator =(Node& node){        // 대입 연산자 오버로딩
        r = node.r;
        c = node.c;
    }
}Node;

bool check_range(Node& node, int size){
    if(node.r < 0 || node.r >= size) return false;
    if(node.c < 0 || node.c >= size) return false;
    return true;
}

bool check_visit(Node& node1, Node& node2, vector<tuple<int, int, int, int>>& v){
    for(int i=0; i<v.size(); i++){
        // 양방향
        Node n1(get<0>(v[i]), get<1>(v[i]));
        Node n2(get<2>(v[i]), get<3>(v[i]));
        if(node1 == n1 && node2 == n2) return false;
        else if(node1 == n2 && node2 == n1) return false;
    }
    // 없으면 추가
    v.push_back(make_tuple(node1.r, node1.c, node2.r, node2.c));
    return true;
}

int solution(string dirs) {
    int answer = 0;
    const int size = 11;          // 10 * 10 board
    vector<tuple<int, int, int, int>> visit;     // 방문 이력(튜플 이용)
    
    // 진행
    Node cur(5, 5);        // x, y = (0, 0)
    for(int i=0; i<dirs.length(); i++){
        Node next(cur);
        switch(dirs[i]){
            case 'U': next.r--;
                break;
            case 'D': next.r++;
                break;
            case 'L': next.c--;
                break;
            case 'R': next.c++;
                break;
        }
        if(!check_range(next, size)) continue;      // 범위 검사
        if(check_visit(cur, next, visit)) answer++;
        cur = next;
    }
    
    return answer;      // 처음 걸어본 길의 길이
}