2020 KAKAO BLIND RECRUITMENT - 블록 이동하기 : set에서 unordered_set으로 바꿔서 풀어보기

문득, 트리 구조(Tree)로 이루어진 set과 해쉬 테이블(Hash Table)로 이루어진 unordered_set의

속도 차이를 손쉽게 경험할 수 있을 것 같아서 기존의 코드를 수정하고 제출해보았다.

* 수정 전 실행 결과(set을 이용) :

* 수정 후 실행 결과(unordered_set을 이용) : 

모든 테스트 케이스에 대해서 유의미한 속도 향상을 보였다.


아래는 수정한 코드이다.
https://github.com/JAlthea/Algorithm/blob/master/BFS/Programmers%20%EB%B8%94%EB%A1%9D%20%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0.cpp


#include <vector>
#include <queue>
#include <unordered_set>
#include <algorithm>
using namespace std;

struct hashFuction {
    size_t operator()(const vector<int> &a) const {
        int resultA = 0;
        int digit = 1;
        for (int i=0; i<4; i++)
        {
            resultA += a[i] * digit;
            digit *= 10;
        }
        return resultA;
    }
};

int solution(vector<vector<int>> board) {
    const int N = board.size() - 1;
    const int dy[] = { 0, 1, -1, 0 };
    const int dx[] = { 1, 0, 0, -1 };
    int answer = 0;
    unordered_set<vector<int>, hashFuction> checkBoard;    //좌표 중복체크를 위함
 
    queue<vector<int>> q;
    q.push({0, 0, 0, 0, 1});    // { 시간, Y1좌표, X1좌표, Y2좌표, X2좌표 }
    while (!q.empty())
    {
        vector<int> v = q.front(); q.pop();
        int time = v[0];
        int y1 = min(v[1], v[3]);
        int x1 = min(v[2], v[4]);
        int y2 = max(v[1], v[3]);
        int x2 = max(v[2], v[4]);
     
        if (y1 == N && x1 == N)
            return time;
        if (y2 == N && x2 == N)
            return time;
     
        if (checkBoard.find({y1, x1, y2, x2}) != checkBoard.end())
            continue;
        checkBoard.insert({y1, x1, y2, x2});
     
        for (int i=0; i<4; i++) //로봇의 4방향 이동
        {
            int ny1 = y1 + dy[i];
            int nx1 = x1 + dx[i];
            int ny2 = y2 + dy[i];
            int nx2 = x2 + dx[i];
         
            if (ny1 < 0 || nx1 < 0 || ny2 < 0 || nx2 < 0)
                continue;
            if (ny1 > N || nx1 > N || ny2 > N || nx2 > N)
                continue;
            if (board[ny1][nx1] == 1 || board[ny2][nx2] == 1)
                continue;
         
            q.push({time + 1, ny1, nx1, ny2, nx2});
        }
     
        if (y1 == y2)   //로봇이 수평으로 놓여있는 경우의 회전
        {
            int ry1[] = {1, -1, 0, 0};
            int rx1[] = {1, 1, 0, 0};
            int ry2[] = {0, 0, -1, 1};
            int rx2[] = {0, 0, -1, -1};
            int cy1[] = {1, -1, 0, 0};
            int cx1[] = {0, 0, 0, 0};
            int cy2[] = {0, 0, -1, 1};
            int cx2[] = {0, 0, 0, 0};
            for (int i=0; i<4; i++)
            {
                //다음 좌표
                int ny1 = y1 + ry1[i];
                int nx1 = x1 + rx1[i];
                int ny2 = y2 + ry2[i];
                int nx2 = x2 + rx2[i];
             
                //회전 시 검사용 좌표
                int my1 = y1 + cy1[i];
                int mx1 = x1 + cx1[i];
                int my2 = y2 + cy2[i];
                int mx2 = x2 + cx2[i];
             
                if (my1 < 0 || mx1 < 0 || my2 < 0 || mx2 < 0)
                    continue;
                if (my1 > N || mx1 > N || my2 > N || mx2 > N)
                    continue;
                if (board[my1][mx1] == 1 || board[my2][mx2] == 1)
                    continue;
                if (ny1 < 0 || nx1 < 0 || ny2 < 0 || nx2 < 0)
                    continue;
                if (ny1 > N || nx1 > N || ny2 > N || nx2 > N)
                    continue;
                if (board[ny1][nx1] == 1 || board[ny2][nx2] == 1)
                    continue;
             
                q.push({time + 1, ny1, nx1, ny2, nx2});
            }
        }
     
        if (x1 == x2)   //로봇이 수직으로 놓여있는 경우의 회전
        {
            int ry1[] = {1, 1, 0, 0};
            int rx1[] = {1, -1, 0, 0};
            int ry2[] = {0, 0, -1, -1};
            int rx2[] = {0, 0, 1, -1};
            int cy1[] = {0, 0, 0, 0};
            int cx1[] = {1, -1, 0, 0};
            int cy2[] = {0, 0, 0, 0};
            int cx2[] = {0, 0, 1, -1};
            for (int i=0; i<4; i++)
            {
                //다음 좌표
                int ny1 = y1 + ry1[i];
                int nx1 = x1 + rx1[i];
                int ny2 = y2 + ry2[i];
                int nx2 = x2 + rx2[i];
             
                //회전 시 검사용 좌표
                int my1 = y1 + cy1[i];
                int mx1 = x1 + cx1[i];
                int my2 = y2 + cy2[i];
                int mx2 = x2 + cx2[i];             
             
                if (my1 < 0 || mx1 < 0 || my2 < 0 || mx2 < 0)
                    continue;
                if (my1 > N || mx1 > N || my2 > N || mx2 > N)
                    continue;
                if (board[my1][mx1] == 1 || board[my2][mx2] == 1)
                    continue;
                if (ny1 < 0 || nx1 < 0 || ny2 < 0 || nx2 < 0)
                    continue;
                if (ny1 > N || nx1 > N || ny2 > N || nx2 > N)
                    continue;
                if (board[ny1][nx1] == 1 || board[ny2][nx2] == 1)
                    continue;
             
                q.push({time + 1, ny1, nx1, ny2, nx2});
            }         
        }
    }
 
    return -1;
}