Life Engineering
[프로그래머스] 블록 이동하기 (C++) 본문
https://programmers.co.kr/learn/courses/30/lessons/60063
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
struct Robot{
pair<int,int> a;
pair<int,int> b;
int cnt;
};
int solution(vector<vector<int>> board) {
int answer = 0;
int N=board.size()-1;
bool visited[101][101][101][101];
memset(visited, false, sizeof(visited));
queue<Robot> q;
q.push({{0,0},{0,1},0});
visited[0][0][0][1]=true;
while (!q.empty()){
Robot r=q.front();
q.pop();
int x1=r.a.first;
int y1=r.a.second;
int x2=r.b.first;
int y2=r.b.second;
int dist=r.cnt;
if ((x1==N && y1==N) || (x2==N && y2==N)){
answer=dist;
break;
}
for (int i=0; i<4; i++){
int nx1=x1+dx[i];
int ny1=y1+dy[i];
int nx2=x2+dx[i];
int ny2=y2+dy[i];
if (nx1<0 || ny1<0 || nx2<0 || ny2<0 || nx1>N || ny1>N || nx2>N || ny2>N)
continue;
if (!visited[nx1][ny1][nx2][ny2] && board[nx1][ny1]==0 && board[nx2][ny2]==0){
visited[nx1][ny1][nx2][ny2]=true;
q.push({{nx1,ny1}, {nx2,ny2}, dist+1});
}
}
if (y2-y1==1){ //가로
if (x1>0 && board[x1-1][y1]==0 && board[x1-1][y1+1]==0){
if (!visited[x1-1][y1][x1][y1]){
visited[x1-1][y1][x1][y1]=true;
q.push({{x1-1,y1},{x1,y1},dist+1});
}
if (!visited[x1-1][y1+1][x2][y2]){
visited[x1-1][y1+1][x2][y2]=true;
q.push({{x1-1,y1+1},{x2,y2},dist+1});
}
}
if (x1<N && board[x1+1][y1]==0 && board[x1+1][y1+1]==0){
if (!visited[x1][y1][x1+1][y1]){
visited[x1][y1][x1+1][y1]=true;
q.push({{x1,y1},{x1+1,y1}, dist+1});
}
if (!visited[x2][y2][x1+1][y1+1]){
visited[x2][y2][x1+1][y1+1]=true;
q.push({{x2,y2},{x1+1,y1+1},dist+1});
}
}
}
else if (x2-x1==1){ //세로
if (y1>0 && board[x1][y1-1]==0 && board[x1+1][y1-1]==0){
if (!visited[x1][y1-1][x1][y1]){
visited[x1][y1-1][x1][y1]=true;
q.push({{x1,y1-1}, {x1,y1}, dist+1});
}
if (!visited[x1+1][y1-1][x2][y2]){
visited[x1+1][y1-1][x2][y2]=true;
q.push({{x1+1,y1-1}, {x2,y2}, dist+1});
}
}
if (y1<N && board[x1][y1+1]==0 && board[x1+1][y1+1]==0){
if (!visited[x1][y1][x1][y1+1]){
visited[x1][y1][x1][y1+1]=true;
q.push({{x1,y1},{x1,y1+1}, dist+1});
}
if (!visited[x2][y2][x1+1][y1+1]){
visited[x2][y2][x1+1][y1+1]=true;
q.push({{x2,y2}, {x1+1,y1+1}, dist+1});
}
}
}
}
return answer;
}
상당히 까다로운 문제였다 .. 거의 하드코딩으로 푼 듯..ㅜㅜ
로봇은 항상 수평, 또는 수직으로만 놓이기 때문에, 충돌 확인을 해야 하는 후보칸은 회전축을 기준으로 대각선 방향에 있는 칸 4개입니다.
-> 90도 회전 하려면 가로 방향이면 위, 아래 가로방향이 비어있는지 확인 , 세로 방향이면 왼, 오 세로방향이 비어있는지 확인해야 한다. 한쪽이 모두 비어있어야 회전이 가능하다.
방문 표시를 4차원 배열 이용해서 했다. 사실 [x][y][direction] 이렇게 하는 방법도 있겠다. 푸는 거에 집중하느라 최적화는 하지 못했다.
'Problem Solving' 카테고리의 다른 글
[BOJ 1963] 소수 경로 (Java) (0) | 2022.01.13 |
---|---|
[BOJ 2589] 보물섬 (JAVA) (0) | 2022.01.04 |
[BOJ 17142] 연구소 3 (C++) (0) | 2021.12.15 |
[프로그래머스] 피로도 (C++) (0) | 2021.12.06 |
[프로그래머스] 방금그곡 (C++) (0) | 2021.11.28 |