[C++로 풀이] 블록 이동하기 (BFS, 해시 함수)⭐⭐⭐
카테고리: Programmers
태그: Coding Test Algorithm
📌 블록 이동하기
난이도 ⭐⭐⭐
🚀 문제
🚀 내 풀이
문제는 일반적인 BFS 문제 풀듯이 풀면 된다. 그러나 주의 깊게 생각해야 할 부분은 다음과 같다.
- 1️⃣ 로봇은 회전이 가능하다는 점! 현재 위치에서 로봇이 회전된 위치들 또한 큐에 삽입하여야 한다.
- 2️⃣ 로봇은 두 파트로 이루어져 있기 때문에 2 개의 좌표를 차지한다. 따라서 방문 체크를 어떻게 할 것인지 신경 써야 한다. 로봇이 “두 파트 동시에 있었던 두 좌표”는 재방문하면 최단경로를 구할 수 없기 떄문에 재방문 하지 않도록 해야 한다.
- 2 가지 방법으로 풀었다. 2 개의 코드 모두 다 살펴볼 것이다.
- 방향까지 고려한 3 차원 배열로 방문 체크하는 방법. 로봇의 두 파트는 왼쪽, 오른쪽 혹은 위쪽 아래쪽으로 ‘구분’할 수 가 있다. 따라서 방향까지 고려하여 두 파트 각각 좌표 방문 체크를 해주는 것.
- 두 파트(위치)를 로봇 구조체로 묶어 로봇 그 자체를 해시 테이블에 보관하여 방문 체크 하는 방법. 즉, 로봇 구조체 그 자체가 이미 해시테이블에 저장이 되어있는지 아닌지로 방문 체크를 한다.
- 2 가지 방법으로 풀었다. 2 개의 코드 모두 다 살펴볼 것이다.
특히 이.. ‘회전’을 구현하는 부분이 좀 까다로웠다.😥
- 로봇이 1 초로 움직여 갈 수 있는 위치들
- 4 가지 종류의 “이동” : 상, 하, 좌, 우
- 로봇의 두 파트 모두가 갈 수 있는 곳이어야 한다.
- 4 가지 종류의 “90도 회전” : 상, 하, 좌, 우
- 가로 방향인 로봇의 경우 (90도 회전이므로 상하 회전만 가능)
- 위로 회전하는 2 가지 경우 모두 위 두칸, 아래로 회전하는 2 가지 경우 모두 아래 두칸이 막혀있지 않아야 한다.
- 회전하여 옮겨질 일부 한 파트가 회전하여 갈 예정인 곳도 갈 수 있는 곳이어야 한다.
- 세로 방향인 로봇의 경우 (90도 회전이므로 좌우 회전만 가능)
- 오른쪽으로 회전하는 2 가지 경우 모두 오른쪽 두 칸, 왼쪽으로 회전하는 2 가지 경우 모두 왼쪽 두 칸이 막혀있지 않아야 한다.
- 회전하여 옮겨질 일부 한 파트가 회전하여 갈 예정인 곳도 갈 수 있는 곳이어야 한다.
- 가로 방향인 로봇의 경우 (90도 회전이므로 상하 회전만 가능)
- 4 가지 종류의 “이동” : 상, 하, 좌, 우
최대 8 개의 로봇 위치를 큐에 삽입할 수 있다. 이 8 가지 후보를 로봇이 추후 갈 수 있는지 검사를 모두 진행해야 한다.
🔥 3 차원 배열로 방문 체크한 풀이 ⭕
#include <string>
#include <vector>
#include <queue>
using namespace std;
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
// 상하좌우
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };
int N;
// 하나의 위치 좌표
struct Pos {
int y; // 행
int x; // 열
int dir; // 로봇의 중심에서 어느쪽에 있는지 그 방향 ⭐
};
// 로봇
struct Robot {
Pos part1; // 로봇의 일부 1 의 위치와 방향
Pos part2; // 로봇의 일부 2 의 위치와 방향
int time; // 현재까지 걸린 시간 (배열 안쓰고 구조체에 저장했다.)
};
// 두 part1, part2 위치가 board 에서 벗어난 곳은 아닌지, 벽은 아닌지 검사
// 즉 기본적으로 갈 수 있는 곳인지 검사
bool possible(vector<vector<int>> board, Pos part1, Pos part2) {
// 두 위치 다 범위에서 벗어난 곳인지
if (part1.y < 0 || part1.y >= N || part1.x < 0 || part1.x >= N ||
part2.y < 0 || part2.y >= N || part2.x < 0 || part2.x >= N)
return false;
// 두 위치 다 벽은 아닌지
if (board[part1.y][part1.x] == 1 ||
board[part2.y][part2.x] == 1)
return false;
// 두 위치 모두 다 범위 내 + 벽이 아니면 true
return true;
}
int solution(vector<vector<int>> board) {
int answer = 0;
N = board.size();
queue<Robot> q;
// 큐 삽입(예약) 체크 배열.
// 로봇은 위치 좌표를 2 개를 쓰고, 또한 회전을 하기 때문에 방문 체크를 방향까지 더한 3차원 배열로 한다.
// 로봇을 이루는 두 위치 모두 따로따로 방문 체크를 진행할 것이다.
bool checked[100][100][4] = { false };
// 로봇의 시작 상태
// 일부1 : (0, 0) 로봇의 왼쪽 파트
// 일부2 : (0, 1) 로봇의 오른쪽 파트
Robot start{ { 0, 0, LEFT }, { 0, 1, RIGHT }, 0 };
checked[0][0][LEFT] = true;
checked[0][1][RIGHT] = true;
q.push(start);
while (!q.empty()) {
// 방문
Robot now = q.front();
q.pop();
// 로봇이 목적지에 도착했다면(로봇의 두 파트 중 하나라도 도착했다면)
if (now.part1.y == N - 1 && now.part1.x == N - 1 || now.part2.y == N - 1 && now.part2.x == N - 1) {
answer = now.time;
break;
}
/* 예약 : 이동 */
for (int i = 0; i < 4; ++i) {
// 다음 방문 위치 후보 (로봇의 두 파트 각각의 위치)
Pos next_part_1{ now.part1.y + dy[i], now.part1.x + dx[i], now.part1.dir };
Pos next_part_2{ now.part2.y + dy[i], now.part2.x + dx[i], now.part2.dir };
// 후보 검사
if (!possible(board, next_part_1, next_part_2)) // 두 위치 모두 다 범위 내 & 벽이 아니어야 한다.
continue;
if (checked[next_part_1.y][next_part_1.x][next_part_1.dir] && checked[next_part_2.y][next_part_2.x][next_part_2.dir]) // 두 위치와 방향 모두 다 큐에 들어간적이 없어야 한다.
continue;
Robot next{ next_part_1, next_part_2, now.time + 1 };
q.push(next);
checked[next.part1.y][next.part1.x][next.part1.dir] = true; // 파트1 예약 체크
checked[next.part2.y][next.part2.x][next.part2.dir] = true; // 파트2 예약 체크
}
/* 예약 : 회전 */
if (now.part1.dir == LEFT) { // 현재 로봇이 가로로 놓여있다면
// 1. 위로 회전
Pos up_left{ now.part1.y - 1, now.part1.x, UP };
Pos up_right{ now.part2.y - 1, now.part2.x, UP };
if (possible(board, up_left, up_right)) { // up_left, up_right 위쪽 두칸이 모두 위치 모두 다 범위 내 & 벽이 아니어야 한다. (회전할 때 가로막히면 안된다.)
// 1-1. 왼쪽을 축으로 위로 회전
if (!checked[up_left.y][up_left.x][UP] || !checked[now.part1.y][now.part1.x][DOWN]) { // 왼쪽 파트를 축으로 회전했을 때 다음 위치 up_left, now.part1(기존)
q.push({ up_left, { now.part1.y, now.part1.x, DOWN } , now.time + 1});
checked[up_left.y][up_left.x][UP] = true;
checked[now.part1.y][now.part1.x][DOWN] = true;
}
// 1-2. 오른쪽을 축으로 위로 회전
if (!checked[up_right.y][up_right.x][UP] || !checked[now.part2.y][now.part2.x][DOWN]) { // 오른쪽 파트를 축으로 회전했을 때 다음 위치 up_right, now.part2(기존)
q.push({ up_right, { now.part2.y, now.part2.x, DOWN } , now.time + 1 });
checked[up_right.y][up_right.x][UP] = true;
checked[now.part2.y][now.part2.x][DOWN] = true;
}
}
// 2. 아래로 회전
Pos down_left{ now.part1.y + 1, now.part1.x, DOWN };
Pos down_right{ now.part2.y + 1, now.part2.x, DOWN };
if (possible(board, down_left, down_right)) {
// 2-1. 왼쪽을 축으로 아래로 회전
if (!checked[down_left.y][down_left.x][DOWN] || !checked[now.part1.y][now.part1.x][UP]) {
q.push({ { now.part1.y, now.part1.x, UP } , down_left, now.time + 1 });
checked[down_left.y][down_left.x][DOWN] = true;
checked[now.part1.y][now.part1.x][UP] = true;
}
// 2-2. 오른쪽을 축으로 아래로 회전
if (!checked[down_right.y][down_right.x][DOWN] || !checked[now.part2.y][now.part2.x][UP]) {
q.push({ { now.part2.y, now.part2.x, UP } , down_right, now.time + 1 });
checked[down_right.y][down_right.x][DOWN] = true;
checked[now.part2.y][now.part2.x][UP] = true;
}
}
}
if (now.part1.dir == UP) { // 현재 로봇이 세로로 놓여있다면
// 1. 왼쪽으로 회전
Pos left_up{ now.part1.y, now.part1.x - 1, LEFT };
Pos left_down{ now.part2.y, now.part2.x - 1, LEFT };
if (possible(board, left_up, left_down)) {
// 1-1. 위쪽을 축으로 왼쪽으로 회전
if (!checked[left_up.y][left_up.x][LEFT] || !checked[now.part1.y][now.part1.x][RIGHT]) {
q.push({ left_up, { now.part1.y, now.part1.x, RIGHT } , now.time + 1 });
checked[left_up.y][left_up.x][LEFT] = true;
checked[now.part1.y][now.part1.x][RIGHT] = true;
}
// 1-2. 아래쪽을 축으로 왼쪽으로 회전
if (!checked[left_down.y][left_down.x][LEFT] || !checked[now.part2.y][now.part2.x][RIGHT]) {
q.push({ left_down, { now.part2.y, now.part2.x, RIGHT } , now.time + 1 });
checked[left_down.y][left_down.x][LEFT] = true;
checked[now.part2.y][now.part2.x][RIGHT] = true;
}
}
// 2. 오른쪽으로 회전
Pos right_up{ now.part1.y, now.part1.x + 1, RIGHT };
Pos right_down{ now.part2.y, now.part2.x + 1, RIGHT };
if (possible(board, right_up, right_down)) {
// 2-1. 위쪽을 축으로 오른쪽으로 회전
if (!checked[right_up.y][right_up.x][RIGHT] || !checked[now.part1.y][now.part1.x][LEFT]) {
q.push({ { now.part1.y, now.part1.x, LEFT } , right_up, now.time + 1 });
checked[right_up.y][right_up.x][RIGHT] = true;
checked[now.part1.y][now.part1.x][LEFT] = true;
}
// 2-1. 아래쪽을 축으로 오른쪽으로 회전
if (!checked[right_down.y][right_down.x][RIGHT] || !checked[now.part2.y][now.part2.x][LEFT]) {
q.push({ { now.part2.y, now.part2.x, LEFT } , right_down, now.time + 1 });
checked[right_down.y][right_down.x][RIGHT] = true;
checked[now.part2.y][now.part2.x][LEFT] = true;
}
}
}
}
return answer;
}
3 차원 배열을 쓰지 않고 2 차원 배열, 즉 위치 좌표로만 방문 체크를 했다면 로봇이 위 그림에서처럼 1번, 2번 이렇게 움직였다면 3 번은 이미 방문했던 곳으로 판단되어 로봇이 3 번 위치로 이동하지 못한다. 실제로 가능해야하는데도 말이다. 3 번의 두 일부분이 각각 1번, 2번에 의해 방문 처리가 되었기 때문이다. 따라서 배열로 방문 체크를 하기 위해선 “방향” 같이 체크해야할 정보가 더 필요하다. 3 차원 배열을 썼다면 1 번에서는 UP, 2 번에서도 UP 이었을테니 3 번에서 동일한 좌표가 각각 LEFT, RIGHT 방향일 떄는 방문된적이 없는 것이므로 로봇이 3 번 위치로 이동하는 것이 가능해진다.
🔥 해시를 사용하여 방문 체크한 풀이(+ 커스텀 해시함수) ⭕
#include <string>
#include <vector>
#include <unordered_set>
#include <queue>
using namespace std;
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
// 상하좌우
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };
int N;
// 하나의 위치 좌표
struct Pos {
int y; // 행
int x; // 열
int dir; // 로봇의 중심에서 어느쪽에 있는지 그 방향 ⭐
};
// 로봇
struct Robot {
Pos part1; // 로봇의 일부 1 의 위치와 방향
Pos part2; // 로봇의 일부 2 의 위치와 방향
int time; // 현재까지 걸린 시간
// 해시에 필요한 == 연산자 오버로딩
bool operator == (const Robot& other) const {
bool condition1 = part1.y == other.part1.y && part1.x == other.part1.x;
bool condition2 = part2.y == other.part2.y && part2.x == other.part2.x;
bool condition3 = part1.y == other.part2.y && part1.x == other.part2.x;
bool condition4 = part2.y == other.part1.y && part2.x == other.part1.x;
if (condition1 && condition2 || condition3 && condition4)
return true;
return false;
}
};
// 커스텀 해시 함수
struct MyHash {
size_t operator()(const Robot& robot) const {
hash<int> hash_func; // C++ 에서 제공하는 기본 자료형 데이터에 대해 사용할 수 있는 해시함수
return hash_func(robot.part1.y) ^ robot.part1.x ^ robot.part2.y + hash_func(robot.part2.x); // XOR과 C++ 제공 해시 함수 짬뽕.. 일단 이런 수준으로 해시 함수를 대충 만들어봤는데 다행히 통과는 하였다..
}
};
// 두 part1, part2 위치가 board 에서 벗어난 곳은 아닌지, 벽은 아닌지 검사
// 즉 기본적으로 갈 수 있는 곳인지 검사
bool possible(vector<vector<int>> board, Pos part1, Pos part2) {
// 두 위치 다 범위에서 벗어난 곳인지
if (part1.y < 0 || part1.y >= N || part1.x < 0 || part1.x >= N ||
part2.y < 0 || part2.y >= N || part2.x < 0 || part2.x >= N)
return false;
// 두 위치 다 벽은 아닌지
if (board[part1.y][part1.x] == 1 ||
board[part2.y][part2.x] == 1)
return false;
// 두 위치 모두 다 범위 내 + 벽이 아니면 true
return true;
}
int solution(vector<vector<int>> board) {
int answer = 0;
N = board.size();
queue<Robot> q;
unordered_set<Robot, MyHash> checked; // ⭐방문 체크를 해시테이블로⭐
// 로봇의 시작 상태
// 일부1 : (0, 0) 로봇 중심의 왼쪽
// 일부2 : (0, 1) 로봇 중심의 오른쪽
Robot start{ { 0, 0, LEFT }, { 0, 1, RIGHT }, 0 };
checked.insert(start); // ⭐ 방문 체크
q.push(start);
while (!q.empty()) {
// 방문
Robot now = q.front();
q.pop();
// 로봇이 목적지에 도착했다면(로봇의 두 파트 중 하나라도 도착했다면)
if (now.part1.y == N - 1 && now.part1.x == N - 1 || now.part2.y == N - 1 && now.part2.x == N - 1) {
answer = now.time;
break;
}
/* 예약 : 이동 */
for (int i = 0; i < 4; ++i) {
Pos next_part_1{ now.part1.y + dy[i], now.part1.x + dx[i], now.part1.dir };
Pos next_part_2{ now.part2.y + dy[i], now.part2.x + dx[i], now.part2.dir };
Robot next{ next_part_1, next_part_2, now.time + 1 };
if (!possible(board, next_part_1, next_part_2))
continue;
if (checked.find(next) != checked.end()) // ⭐ 방문한적이 없다면 (즉, 해시테이블에 없다면)
continue;
q.push(next);
checked.insert(next); // ⭐ 방문 체크
}
/* 예약 : 회전 */
if (now.part1.dir == LEFT) {
Pos up_left{ now.part1.y - 1, now.part1.x, UP };
Pos up_right{ now.part2.y - 1, now.part2.x, UP };
if (possible(board, up_left, up_right)) {
Robot next1{ up_left, { now.part1.y, now.part1.x, DOWN } , now.time + 1 };
if (checked.find(next1) == checked.end()) {
q.push(next1);
checked.insert(next1);
}
Robot next2{ up_right, { now.part2.y, now.part2.x, DOWN } , now.time + 1 };
if (checked.find(next2) == checked.end()) {
q.push(next2);
checked.insert(next2);
}
}
Pos down_left{ now.part1.y + 1, now.part1.x, DOWN };
Pos down_right{ now.part2.y + 1, now.part2.x, DOWN };
if (possible(board, down_left, down_right)) {
Robot next1{ { now.part1.y, now.part1.x, UP }, down_left, now.time + 1 };
if (checked.find(next1) == checked.end()) {
q.push(next1);
checked.insert(next1);
}
Robot next2{ { now.part2.y, now.part2.x, UP } , down_right, now.time + 1 };
if (checked.find(next2) == checked.end()) {
q.push(next2);
checked.insert(next2);
}
}
}
if (now.part1.dir == UP) {
Pos left_up{ now.part1.y, now.part1.x - 1, LEFT };
Pos left_down{ now.part2.y, now.part2.x - 1, LEFT };
if (possible(board, left_up, left_down)) {
Robot next1{ left_up, { now.part1.y, now.part1.x, RIGHT } , now.time + 1 };
if (checked.find(next1) == checked.end()) {
q.push(next1);
checked.insert(next1);
}
Robot next2{ left_down, { now.part2.y, now.part2.x, RIGHT } , now.time + 1 };
if (checked.find(next2) == checked.end()) {
q.push(next2);
checked.insert(next2);
}
}
Pos right_up{ now.part1.y, now.part1.x + 1, RIGHT };
Pos right_down{ now.part2.y, now.part2.x + 1, RIGHT };
if (possible(board, right_up, right_down)) {
Robot next1{ { now.part1.y, now.part1.x, LEFT } , right_up, now.time + 1 };
if (checked.find(next1) == checked.end()) {
q.push(next1);
checked.insert(next1);
}
Robot next2{ { now.part2.y, now.part2.x, LEFT } , right_down, now.time + 1 };
if (checked.find(next2) == checked.end()) {
q.push(next2);
checked.insert(next2);
}
}
}
}
return answer;
}
첫 번째 풀이처럼 로봇의 파트1, 파트2를 따로 따로 방문 체크하지 않고 Robot 구조체를 통째로 unordered_set 해시 테이블에 넣고 해시값을 통하여 방문 체크를 한다.
// 로봇
struct Robot {
Pos part1; // 로봇의 일부 1 의 위치와 방향
Pos part2; // 로봇의 일부 2 의 위치와 방향
int time; // 현재까지 걸린 시간
// 해시에 필요한 == 연산자 오버로딩
bool operator == (const Robot& other) const {
bool condition1 = part1.y == other.part1.y && part1.x == other.part1.x;
bool condition2 = part2.y == other.part2.y && part2.x == other.part2.x;
bool condition3 = part1.y == other.part2.y && part1.x == other.part2.x;
bool condition4 = part2.y == other.part1.y && part2.x == other.part1.x;
if (condition1 && condition2 || condition3 && condition4)
return true;
return false;
}
};
// 커스텀 해시 함수
struct MyHash {
size_t operator()(const Robot& robot) const {
hash<int> hash_func; // C++ 에서 제공하는 기본 자료형 데이터에 대해 사용할 수 있는 해시함수
return hash_func(robot.part1.y) ^ robot.part1.x ^ robot.part2.y + hash_func(robot.part2.x); // XOR과 C++ 제공 해시 함수 짬뽕.. 일단 이런 수준으로 해시 함수를 대충 만들어봤는데 다행히 통과는 하였다..
}
};
두 위치의 x, y 총 4 개의 파라미터가 전부 일치해야 같은 로봇으로 인식될 수 있도록(동일한 해시값을 도출하도록) 하였다. 이렇게 해시 함수와 == 연산자 오버로딩을 만들어두고 방문 체크를 하면 된다! 고유한 해시값을 도출할 수 있게끔 해시 함수를 잘 만드는 방법에 대해선 나중에 공부를 한번 해봐야할 것 같다.
[STL 컨테이너] set, unordered_set (+ map)에 사용자 정의 구조체 혹은 객체 담기
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기