[프로그래머스] Level 1. 방문길이

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

프로그래머스

 

나의 해결방법

vector<vector<string>> matrix 를 선언하여, 해당 점에서 어느 방향으로 이동했는지를 "UDLR" 형식으로 저장했다. 

(2,0) > (2,1) 로 오른쪽 이동 했을 경우 matrix[2][0] 을 확인하여 문자열 안에 'R' 이 들어있다면 이미 방문했다는 의미이다.

아쉬운 점은, inverse_dir 과 dir을 찾을 때, 배열에 미리 저장해놓았으면 더 코드 길이를 짧게 만들 수 있겠다는 생각이 든다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(string dirs) {
    
    vector<vector<string>> matrix(11, vector<string>(11,""));
    
    int distance = 0;
    pair<int,int> pos(5,5);
    
    for(int i = 0; i<dirs.size(); i++){
        int xDir = 0;
        int yDir = 0;
        char inverse_dir ;
        if(dirs[i] == 'U') {
            yDir = 1;
            inverse_dir = 'D';
        }
        else if(dirs[i] == 'D'){
            yDir = -1;
            inverse_dir ='U';
        } 
        else if(dirs[i] == 'R'){
             xDir = 1;
            inverse_dir = 'L';
        } 
        else if(dirs[i] == 'L'){
            xDir = -1;
            inverse_dir ='R';
        } 
        
        pair<int,int> expected (pos.first + xDir , pos.second + yDir);
        if(expected.first < 0|| expected.first > 10 || expected.second < 0 || expected.second > 10) continue;
        
        string walked_dir = matrix[pos.first][pos.second];
        auto value = find(walked_dir.begin(), walked_dir.end(), dirs[i]);
        if(value == walked_dir.end()){
            distance ++;
            matrix[pos.first][pos.second] += dirs[i];
            matrix[expected.first][expected.second] += inverse_dir;
        }
        
        pos = expected;
        
    }
    
    return distance;
}

 

다른 풀이

책에서는 vector<vector<vector<bool>> 로 선언했는데, 이것도 좋은것같다.

그리고 다른사람 풀이를 보다가 set을 이용한 정말 혁신적인 답안을 발견했다. 원래는 포스팅을 안하려했는데 이것때문에 포스팅을 하게됐다. 

1. (2,3) 을 숫자 20003 으로 변환함으로써 한가지 숫자로 합칠 수 있다는 것이 아이디어가 좋았다.

2. Set을 사용해서 중복값을 알아서 제거함으로써, 하나하나 개수를 셀 필요없이, set의 개수가 곧 지나간 길의 개수가 되게했다. 세상에는 천재가 많다.

 

#include <string>
#include <set>
using namespace std;
int toIdx(char ch){
    switch(ch){
        case 'R': return 0;
        case 'L': return 1;
        case 'U': return 2;
        case 'D': return 3;
    }
}
int solution(string dirs) {
    char ch;
    int answer = 0,i, x=0,y=0,ty,tx,dy[]={0,0,1,-1},dx[]={1,-1,0,0},idx,a,b;
    set<pair<int,int>> ans;
    for(i=0;i<dirs.length();i++) {
        ch = dirs[i];
        idx = toIdx(ch);
        tx = x + dx[idx], ty = y + dy[idx];
        if(!(-5 <= ty && ty <= 5 && -5 <= tx && tx <= 5)) continue;
        a = x*10000+y;
        x = tx, y = ty;
        b = x*10000+y;
        if(ans.find({a,b}) == ans.end() && ans.find({b,a}) == ans.end())
            ans.insert({a,b});
    }
    return answer = (int)ans.size();
}