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

풀이

재밌는 문제다.

좌표상에서 U, D, R, L 조작을 해서 내가 건너간 다리가 처음 다리라면 경우의 수를 추가해주고, 이미 건넜던 다리라면 그냥 건너가기만 하면 된다.

 

핵심은 내가 건너간 다리가 처음 방문한 다리인지 아닌지를 체크하는 것이다.

어떻게 체크할까?

시작 좌표는(0, 0) 에서 U이라는 명령을 받았다면 내가 건너게 될 다리는 다음과 같다.

(0,0) -> (-1,0)

(-1,0) <- (0,0)

이렇게 양방향으로 하는 이유는 둘 다 동일한 다리이기 때문이다.

 

이렇게 건넌 다리를 체크하기 위해서 Node라는 구조체를 만들고, 방문 배열에 해당 Node를 추가하는 방식으로 방문 배열을 만들었다. 다리를 통과할 때 해당 다리를 전에 방문했는지 안 했는지 체크는 배열을 돌면서 다리와 일치하면 이미 건넌 다리고 아니라면 처음 건너는 다리로 구현해주면 된다.

 

다 풀고 다른 사람이 푼 것을 봤는데 아래의 방법도 좋은 방법이다.

1. 방문 배열을 4차원 배열로 설정하는 방법

bool vis[x1][y1][x2][y2];

2. set 자료구조를 이용하는 방법

set<pair<pair<int, int>, pair<int, int> > > s;
//양방향으로 넣어주고
s.insert({{x1,y1},{x2,y2}});
s.insert({{x2,y2},{x1,y1}});
//마지막에 답을 도출할 때 2로 나눠주면 끝
ans = s.size() / 2;

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

struct Node {
public:
    int x1, y1;
    int x2, y2;

    Node(int a, int b, int c, int d) : x1(a), y1(b), x2(c), y2(d) {}
    bool operator==(const Node& other) {
        if(x1 == other.x1 && y1 == other.y1 && x2 == other.x2 && y2 == other.y2) return true;
        if(x1 == other.x2 && y1 == other.y2 && x2 == other.x1 && y2 == other.y1) return true;
        return false;
    }
};

int solution(string dirs) {
    map<char, pair<int, int>> m;
    m['U'] = { -1,0 };
    m['D'] = { 1,0 };
    m['R'] = { 0,1 };
    m['L'] = { 0,-1 };
    int x = 0;
    int y = 0;
    int ans = 0;
    queue<char> q;
    vector<Node> vis;
    for (char c : dirs) q.push(c);
    while (!q.empty()) {
        int nx = x + m[q.front()].first;
        int ny = y + m[q.front()].second;
        q.pop();

        if (nx < -5 || ny < -5 || nx > 5 || ny > 5) continue;
        Node node(x, y, nx, ny);
        bool ok = true;
        for (Node n : vis) {
            if(n == node) {
                ok = false;
                break;
            }
        }
        if (ok) {
            vis.push_back(node);
            ans++;
        }
        x = nx;
        y = ny;
    }
    return ans;
}