[Kakao코딩테스트] 2020-7번-블록이동하기
풀이
ㅠㅠ 오랜만에 진짜 삽질제대로했다… 오랜만에 문제풀었더니 센스가 너무없네. 만약 시간재놓고 푸는거였다면 이거에 매달리다가 다른거 전혀못풀었을듯.
그냥 문제 읽어보고 삼성SW기출이었던 파이프옮기기(원래는 버스이동하기였음) 파이프옮기기1 이문제와 유사하다고 생각하고 항상 오른쪽아래로 향하게 짰다. 나름 최적화한다고 우선순위큐를 쓰고 cmp함수도 직접 만들었다.
하지만! 예제는 맞지만 돌려보니까 테케 2개뺴고 다틀린다! 대충 빙~빙~도는 길하나뺴고 다막아둔게 대부분인것같다.
처음부터 x,y,(따라다니는친구의방향) 이렇게 세팅하고 풀었어야되는데 졸린김에 계속 덧붙여서 풀었다. 그래서 나온게 12가지 방향을 전부 BFS했다. 그리고 반대로 가는 방향일떄 회전하면 대가리위치를 다시 조정해줘야했다.
우웩 더러운코드. 다신보지말자. 그래도 푼게어디야
결과: 테케13 - 4.2ms 테케14 - 2.5ms 나머지 0.3ms이내
코드
BFS [Kakao] 2020-7-블록이동하기
#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
struct cmp{
bool operator()(pair<pair<int,int>,pair<int,int>> a, pair<pair<int,int>,pair<int,int>> b){
if(a.first.first > b.first.first){
return true;
}else if(a.first.first == b.first.first){
if(a.second.first < b.second.first){
return true;
}else if(a.second.first == b.second.first){
if(a.second.second < b.second.second){
return true;
}
return false;
}
return false;
}
return false;
}
};
//0:오른쪽,1:아래,2:왼쪽,3:위로
//4:(가로일때)아래(이후세로),5:(가로일때)왼쪽아래(후세로),6:(세로일때)오른쪽(이후가로),7:(세로일때)오른쪽위(이후가로)
//8:(가로일떄)위(이후세로) 9:(가로일떄)왼쪽위(이후세로) 10:(세로일떄)왼쪽(이후가로) 11:(세로일떄)왼쪽위(이후가로)
const int dx[] = {1,0,-1,0,0,-1,1,1,0,-1,-1,-1};
const int dy[] = {0,1,0,-1,1,1,0,-1,-1,-1,0,-1};
int chk[100][100][2];
int solution(vector<vector<int>> board) {
int answer = 0;
int N = board[0].size();
//{cnt(횟수),state(가로0,세로1)},{x좌표,y좌표}
priority_queue<pair<pair<int,int>,pair<int,int>>,vector<pair<pair<int,int>,pair<int,int>>>,cmp> q;
q.push({ {0 , 0} , {1 , 0} });
chk[0][1][0]=1;
while(!q.empty()){
int cnt=q.top().first.first;
int state=q.top().first.second;
int x = q.top().second.first;
int y = q.top().second.second;
cout<<"cnt:"<<cnt<<" state:"<<state<<" x:"<<x<<" y:"<<y<<'\n';
q.pop();
if(x==N-1 && y==N-1){
answer=cnt;
break;
}
for(int dir=0;dir<12;dir++){
if(dir==4 || dir==5 || dir==8 || dir==9){
//세로면 continue
if(state==1)
continue;
}
if(dir==6 || dir==7 || dir==10 || dir==11){
//가로면 continue
if(state==0)
continue;
}
int nx = x+dx[dir];
int ny = y+dy[dir];
if(nx>=0&&nx<N&&ny>=0&&ny<N&&board[ny][nx]==0){
if(dir==0){
if(state==0 || board[ny-1][nx]==0){
if(chk[ny][nx][state]==0){
chk[ny][nx][state]=1;
q.push({ { cnt+1, state } , { nx, ny } });
}
}
}else if(dir==1){
if(state==1 || board[ny][nx-1]==0){
if(chk[ny][nx][state]==0){
chk[ny][nx][state]=1;
q.push({ { cnt+1, state } , { nx, ny } });
}
}
}else if(dir==2){//왼쪽
if(state==1 && board[ny-1][nx]==0){
if(chk[ny][nx][state]==0){
chk[ny][nx][state]=1;
q.push({ { cnt+1, state } , { nx, ny } });
}
}else if(state==0 && nx>0 && board[ny][nx-1]==0){
if(chk[ny][nx][state]==0){
chk[ny][nx][state]=1;
q.push({ { cnt+1, state } , { nx, ny } });
}
}
}else if(dir==3){//위로
if(state==0 && board[ny][nx-1]==0){
if(chk[ny][nx][state]==0){
chk[ny][nx][state]=1;
q.push({ { cnt+1, state } , { nx, ny } });
}
}else if(state==1 && ny>0 && board[ny-1][nx]==0){
if(chk[ny][nx][state]==0){
chk[ny][nx][state]=1;
q.push({ { cnt+1, state } , { nx, ny } });
}
}
}else if(dir==4){
//4:(가로일때)아래(이후세로)
if(board[ny][nx-1]==0){
if(chk[ny][nx][1]==0){
chk[ny][nx][1]=1;
q.push({ { cnt+1, 1 } , { nx, ny } });
}
}
}else if(dir==5){
//5:(가로일때)왼쪽아래(후세로)
if(board[ny][nx+1]==0){
if(chk[ny][nx][1]==0){
chk[ny][nx][1]=1;
q.push({ { cnt+1, 1 } , { nx, ny } });
}
}
}else if(dir==6){
//6:(세로일때)오른쪽(이후가로)
if(board[ny-1][nx]==0){
if(chk[ny][nx][0]==0){
chk[ny][nx][0]=1;
q.push({ { cnt+1, 0 } , { nx, ny } });
}
}
}else if(dir==7 ){
//7:(세로일때)오른쪽위(이후가로)
if(board[ny+1][nx]==0){
if(chk[ny][nx][0]==0){
chk[ny][nx][0]=1;
q.push({ { cnt+1, 0 } , { nx, ny } });
}
}
}
//추가
else if(dir==8){
//8:(가로일떄)위(이후세로)
if(board[ny][nx-1]==0){
//하지만 대장은 그대로로 한다.
if(chk[y][x][1]==0){
chk[y][x][1]=1;
q.push({ { cnt+1, 1 } , { x, y } });
}
}
}else if(dir==9){
//9:(가로일떄)왼쪽위(이후세로)
if(board[ny][nx+1]==0){
//하지만 대장은 왼쪽으로한다
if(chk[y][x-1][1]==0){
chk[y][x-1][1]=1;
q.push({ { cnt+1, 1 } , { x-1, y } });
}
}
}else if(dir==10){
//10:(세로일떄)왼쪽(이후가로)
if(board[ny-1][nx]==0){
//하지만 대장은 그대로로한다
if(chk[y][x][0]==0){
chk[y][x][0]=1;
q.push({ { cnt+1, 0 } , { x, y } });
}
}
}else if(dir==11){
//11:(세로일떄)왼쪽위(이후가로)
if(board[ny+1][nx]==0){
//하지만 대장은 위로한다
if(chk[y-1][x][0]==0){
chk[y-1][x][0]=1;
q.push({ { cnt+1, 0 } , { x, y-1 } });
}
}
}
}
}
}
return answer;
}
Written on September 6, 2020