오늘 하루동안 너무 많은 시간을 썼지만 정말 어이없게도 숫자 하나를 실수로 못적었고 그걸 찾아내느라 몇시간을 뻘짓을 했던 문제다. 이번 문제는 처음으로 카카오 풀이 해석에서 스크린샷을 가져왔고 2020년도 블라인드에서 나왔던 마지막 문제였다. 마지막 문제답게 굉장히 낮은 정답률을 보유했고 실제로 풀이 자체도 좀 복잡 했었다. 이 문제는 좀 추억이 있는게 입대하기 전에 풀어볼려고 도전해봤다가 손도 못대보고 포기했었던 문제였다. 전역을 하고도 이 문제는 트라우마가 있는지 딱히 건들지를 않았는데 백준 문제들을 많이 풀어보고 DFS/BFS/Simulation 등등 많이 익숙해진 상태에서 다시 문제를 읽어보니 할만하다 생각해서 도전했다.
실제로는 한시간 반? 정도 걸려서 풀었던거 같다. 물론 실수를 빠르게 고쳤을때 가정이지만 앞으로 이런 실수는 절대 안해야겠다. 일반적인 BFS 문제가 아니고 이 문제는 특이하게 두가지의 좌표를 가지고 동시에 움직였어야 했고 백준에서 "두 동전" 이라는 문제가 떠오르게 만들었다.
이 문제를 가장 어렵게 만드는 포인트는 역시 회전인거같다. 난 저 부분을 구현하기 위해 노트북에 회전 방향에 따른 그림을 그려서 좌표를 지정해주고 학습했다. 역시 코테를 풀때 노트는 필수 인거같다. 일반적인 BFS 문제가 아니고 구현이 "굉장히" 빡쌘 문제였기 때문에 많이 어려워 하는것도 인정한다.
다른 사람들의 풀이를 보니깐 Map 을 쓰는 사람도 있었고 (왜 필요했는지는 모른다) 등등 별 짓을 다 하던데 나같은 경우는 4차원 방문 배열이 가장 먼저 생각났다. 이제는 Struct 를 사용하는데 익숙 해졌고 방문배열을 사용할때 좌표를 총 4가지 쓰기 때문에 4차원 방문 배열이 맞지 않나 싶었지만 다른 사람들을 보니 3차원으로 방향만 지정해주고 풀던 사람들도 여럿 봤다.
여기서 또 중요하게 생각했던 부분 중 하나는 방문배열을 확인할때 00 01 만 true 로 해주는게 아니고 01 00 도 true 로 해주는게 시간적인 면에서 훨씬 빨랐을거다. 다행히 시간에 대한 제한은 없어서 풀었지만 다른 사람들의 풀이에 비해 내꺼는 좀 느렸다.
가로 상태의 회전이랑 세로 상태의 회전이 다르기 때문에 계속 신경 써줬어야 했고 솔직히 어려운 문제긴 했다. 풀면서도 구현 부분에서 화가 나것 이딴게 문제인가 생각했을정도 있다.
그래도 확실히 성장한거 같아서 기분이 좋아진 문제였다.
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
struct Drone{
int x1, y1, x2, y2, dist, direction;
};
bool visited[101][101][101][101];
int N, M;
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}};
queue<Drone> q;
int bfs(vector<vector<int>>& board){
N = board.size(), M = board[0].size();
memset(visited,false,sizeof(visited));
q.push({0,0,0,1,0,0}); //좌표 0,0 이랑 0,1 에 가로로 (0) 시작한다
visited[0][0][0][1] = true;
while(!q.empty()){
int size = q.size();
for(int i = 0; i < size; i++){
Drone drone = q.front();
q.pop();
int x1 = drone.x1, y1 = drone.y1, x2 = drone.x2, y2 = drone.y2;
int dist = drone.dist, direction = drone.direction;
//cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
if(x1 == N-1 && y1 == M-1 || x2 == N-1 && y2 == M-1){ //둘 중 어느 칸이라도 마지막에 도달한다면 끝
return dist;
}
for(pair<int,int>& p : dir){ //상하좌우 움직임
int nX1 = x1 + p.first;
int nY1 = y1 + p.second;
int nX2 = x2 + p.first;
int nY2 = y2 + p.second;
//만약 한변이라도 밖으로 나가거나 벽을 부딪친다면 바로 패스
if(nX1 < 0 || nY1 < 0 || nX1 >= N || nY1 >= M || board[nX1][nY1] == 1) continue;
if(nX2 < 0 || nY2 < 0 || nX2 >= N || nY2 >= M || board[nX2][nY2] == 1) continue;
if(visited[nX1][nY1][nX2][nY2]) continue;
q.push({nX1,nY1,nX2,nY2,dist+1,direction});
visited[nX1][nY1][nX2][nY2] = true;
}
if(direction == 0){ //가로 포지션일때 90도 회전
//왼쪽 기준 (왼쪽은 고정이다)
//위쪽으로 90도
int nX2 = x2 - 1;
int nY2 = y2 - 1;
if(nX2 >= 0 && nY2 >= 0 && nX2 < N && nY2 < N){
if(board[nX2][nY2] == 0 && board[nX2][y2] ==0 && !visited[nX2][nY2][x1][y1]){
q.push({nX2,nY2,x1,y1,dist+1,1});
visited[nX2][nY2][x1][y1] = true;
}
}
//아래쪽으로 90도
int nXX2 = x2 + 1;
int nYY2 = y2 - 1;
if(nXX2 >= 0 && nYY2 >= 0 && nXX2 < N && nYY2 < N){
if(board[nXX2][nYY2] == 0 && board[nXX2][y2] == 0 && !visited[x1][y1][nXX2][nYY2]){
q.push({x1,y1,nXX2,nYY2,dist+1,1});
visited[x1][y1][nXX2][nYY2] = true;
}
}
//오른쪽 기준 (오른쪽은 고정이다)
//위쪽으로 90도
int nX1 = x1 - 1;
int nY1 = y1 + 1;
if(nX1 >= 0 && nY1 >= 0 && nX1 < N && nY1 < N){
if(board[nX1][nY1] == 0 && board[nX1][y1] == 0 && !visited[nX1][nY1][x2][y2]){
q.push({nX1,nY1,x2,y2,dist+1,1});
visited[nX1][nY1][x2][y2] = true;
}
}
//아래쪽으로 90도
int nXX1 = x1 + 1;
int nYY1 = y1 + 1;
if(nXX1 >= 0 && nYY1 >= 0 && nXX1 < N && nYY1 < N){
if(board[nXX1][nYY1] == 0 && board[nXX1][y1] == 0 && !visited[x2][y2][nXX1][nYY1]){
q.push({x2,y2,nXX1,nYY1,dist+1,1});
visited[x2][y2][nXX1][nYY1] = true;
}
}
}
if(direction == 1){ //세로 포지션일때 90도 회전
//위쪽 기준 (위쪽은 고정이다)
//왼쪽으로 90도
int nX2 = x2 - 1;
int nY2 = y2 - 1;
if(nX2 >= 0 && nY2 >= 0 && nX2 < N && nY2 < N){
if(board[nX2][nY2] == 0 && board[x2][nY2] == 0 && !visited[nX2][nY2][x1][y1]){
q.push({nX2,nY2,x1,y1,dist+1,0});
visited[nX2][nY2][x1][y1] = true;
}
}
//오른쪽으로 90도
int nXX2 = x2 - 1;
int nYY2 = y2 + 1;
if(nXX2 >= 0 && nYY2 >= 0 && nXX2 < N && nYY2 < N){
if(board[nXX2][nYY2] == 0 && board[x2][nYY2] == 0 && !visited[x1][y1][nXX2][nYY2]){
q.push({x1,y1,nXX2,nYY2,dist+1,0});
visited[x1][y1][nXX2][nYY2] = true;
}
}
//아래쪽 기준 (아래쪽은 고정이다)
//왼쪽으로 90도
int nX1 = x1 + 1;
int nY1 = y1 - 1;
if(nX1 >= 0 && nY1 >= 0 && nX1 < N && nY1 < N){
if(board[nX1][nY1] == 0 && board[x1][nY1] == 0 && !visited[nX1][nY1][x2][y2]){
q.push({nX1,nY1,x2,y2,dist+1,0});
visited[nX1][nY1][x2][y2] = true;
}
}
//오른쪽으로 90도
int nXX1 = x1 + 1;
int nYY1 = y1 + 1;
if(nXX1 >= 0 && nYY1 >= 0 && nXX1 < N && nYY1 < N){
if(board[nXX1][nYY1] == 0 && board[x1][nYY1] == 0 && !visited[x2][y2][nXX1][nYY1]){
q.push({x2,y2,nXX1,nYY1,dist+1,0});
visited[x2][y2][nXX1][nYY1] = true;
}
}
}
}
}
return -1;
}
int solution(vector<vector<int>> board) {
return bfs(board);
}배운점:
1. 사소한 부분이라도 다시 확인하기
2. 시물레이션 잘 따라가기
