https://programmers.co.kr/learn/courses/30/lessons/60063
코딩테스트 연습 - 블록 이동하기
[[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7
programmers.co.kr
풀이
이 문제는 DFS, BFS 모두 풀이가 가능한 문제이다. 글쓴이는 평소 DFS를 많이 이용했기 때문에 이번에는 BFS를 이용하여 풀어보았다. 로봇이 한 칸을 차지하는 것이 아닌 두 칸을 차지하므로 예외처리를 많이 해야하기 때문에 캐치하지 못한 부분이 있어 일부 테스트 케이스를 통과하지 못할 수도 있다. 나도 이 문제를 풀며 내가 생각하지 못한 부분을 예외처리하지 못하여 약간의 시간이 더 걸렸다. 로봇의 현재 위치에서 생각해야할 부분은 네 가지가 있다.
- 다음 위치가 보드를 벗어나는지
- 로봇이 차지하는 두 칸 중 하나도 1이 아닌지
- 이미 현재 위치를 거쳐갔는지
- 회전하는 경우 회전할 때 지나가는 칸이 1이 아닌지
위 네 가지만 예외처리하면 쉽게 풀 수 있는 문제이다. 예외처리만 하면 되는 문제이기 때문에 if, continue 등이 많이 쓰였다.
문제를 풀 때 로봇이 상하좌우로 이동하는 경우, 회전하는 경우를 나누어서 풀었다. 상하좌우로 이동하는 경우는 일반 BFS처럼 풀면 되기 때문에 예외처리가 따로 할 부분이 없었다. 문제는 회전하는 경우였다. 회전하는 경우를 차지하는 두 칸 중에 한 칸이 대각선으로 이동하는 방식으로 생각했다. 그림으로 나타내면 다음과 같다.
위와 같이 이동한다고 할 때 실제로는 2, 4번으로 이동할 수 있지만 1, 3번으로는 이동하지 못한다. 이 부분을 예외처리하기 위해 두 칸의 x좌표나 y좌표 중 하나가 같은 경우에만 올바르게 회전했다고 판단했다. 이 과정을 다른 쪽 칸도 똑같이 진행하였다. 이렇게 회전하는 경우에 갈 수 있는 좌표의 위치를 계산할 수 있다.
소스 코드
#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
struct pos{ //x, y좌표를 가지는 구조체
int x, y;
};
struct element { //큐에 넣을 구조체
pair<pos,pos> position;
int depth;
};
bool visit[101][101][101][101]; //방문배열
int dx[4] = {1, 0, 0, -1}; //dx, dy는 상하좌우로 이동
int dy[4] = {0, 1, -1, 0};
int rx[4] = {1, 1, -1, -1}; //rx, ry는 회전
int ry[4] = {1, -1, 1, -1};
int solution(vector<vector<int>> board) {
int N = board.size();
pair<pos,pos> robot = {{0, 0}, {0, 1}}; ///로봇의 현재 위치
queue<element> q; //BFS에 사용될 큐
q.push({robot, 0}); //현재 위치를 큐에 넣음
visit[robot.first.x][robot.first.y][robot.second.x][robot.second.y] = true; //현재 위치 방문 표시
visit[robot.second.x][robot.second.y][robot.first.x][robot.first.y] = true; //두 칸을 반대로 했을 때도 방문 표시
while(!q.empty()) { //큐가 빌 때까지
element e = q.front(); q.pop();
pair<pos,pos> now = e.position; //현재 위치
for(int d = 0; d < 4; d++) { //상하좌우 방향으로
pair<pos,pos> nxt = {{now.first.x + dx[d], now.first.y + dy[d]}, {now.second.x + dx[d], now.second.y + dy[d]}}; //다음 좌표 위치
if(nxt.first.x < 0 || nxt.first.x >= N) continue; //범위를 벗어나는 경우 건너뛰기
if(nxt.first.y < 0 || nxt.first.y >= N) continue;
if(nxt.second.x < 0 || nxt.second.x >= N) continue;
if(nxt.second.y < 0 || nxt.second.y >= N) continue;
if(board[nxt.first.x][nxt.first.y] || board[nxt.second.x][nxt.second.y]) continue; //만약 두 칸 중에 하나라도 1인 경우 건너뛰기
if(visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y]) continue; //이미 방문한 경우도 건너뛰기
if(visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y]) continue; //로봇 왼쪽 오른쪽이 반대로 됐을 경우도 같음
if((nxt.first.x == N-1 && nxt.first.y == N-1) || (nxt.second.x == N-1 && nxt.second.y == N-1)) { //도착한 경우 방문 횟수 리턴
return e.depth + 1;
}
else { //그렇지 않은 경우 다음 로봇 위치 방문 표시 후 큐에 넣기
visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y] = true;
visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y] = true;
q.push({nxt, e.depth + 1});
}
}
for(int r = 0; r < 4; r++) { //회전하는 경우
pair<pos,pos> nxt = {{now.first.x + rx[r], now.first.y + ry[r]}, {now.second.x, now.second.y}}; //한 쪽 날개 회전
if(nxt.first.x != nxt.second.x && nxt.first.y != nxt.second.y) continue; //만약 한쪽을 대각선으로 회전했을 때 로봇이 차지하는 두 칸이 나란히 있지 않은 경우 건너뛰기
if(nxt.first.x < 0 || nxt.first.x >= N) continue; //범위를 벗어나는 경우 건너뛰기
if(nxt.first.y < 0 || nxt.first.y >= N) continue;
if(nxt.second.x < 0 || nxt.second.x >= N) continue;
if(nxt.second.y < 0 || nxt.second.y >= N) continue;
if(board[now.first.x][now.first.y + ry[r]] || board[now.first.x + rx[r]][now.first.y]) continue; //회전시 지나가는 칸이 1인 경우 건너뛰기
if(board[nxt.first.x][nxt.first.y] || board[nxt.second.x][nxt.second.y]) continue; //차지하는 두 칸중 하나라도 1인 경우 건너뛰기
if(visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y]) continue; //이미 방문한 경우 건너뛰기
if(visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y]) continue;
if((nxt.first.x == N-1 && nxt.first.y == N-1) || (nxt.second.x == N-1 && nxt.second.y == N-1)) { //종료지점 도착시 리턴
return e.depth + 1;
}
else { //그렇지 않은 경우 다음 로봇 위치 방문 표시 후 큐에 넣기
visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y] = true;
visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y] = true;
q.push({nxt, e.depth + 1});
}
}
for(int r = 0; r < 4; r++) { //다른 한 쪽이 회전하는 경우
pair<pos,pos> nxt = {{now.first.x, now.first.y}, {now.second.x + rx[r], now.second.y + ry[r]}}; //다른 한 쪽 날개 회전
if(nxt.first.x != nxt.second.x && nxt.first.y != nxt.second.y) continue; //로봇이 차지하는 두 칸이 나란히 있지 않은 경우 리턴
if(nxt.first.x < 0 || nxt.first.x >= N) continue; //범위를 벗어나는 경우 리턴
if(nxt.first.y < 0 || nxt.first.y >= N) continue;
if(nxt.second.x < 0 || nxt.second.x >= N) continue;
if(nxt.second.y < 0 || nxt.second.y >= N) continue;
if(board[now.second.x][now.second.y + ry[r]] || board[now.second.x + rx[r]][now.second.y]) continue; //회전시 지나가는 칸이 1인 경우 건너뛰기
if(board[nxt.first.x][nxt.first.y] || board[nxt.second.x][nxt.second.y]) continue; //차지하는 두 칸중 하나라도 1인 경우 건너뛰기
if(visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y]) continue;//이미 방문한 경우 건너뛰기
if(visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y]) continue;
if((nxt.first.x == N-1 && nxt.first.y == N-1) || (nxt.second.x == N-1 && nxt.second.y == N-1)) { //종료지점 도착시 리턴
return e.depth + 1;
}
else { //그렇지 않은 경우 다음 로봇 위치 방문 표시 후 큐에 넣기
visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y] = true;
visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y] = true;
q.push({nxt, e.depth + 1});
}
}
}
}같은 코드가 반복되어 비효율적인 부분이 있긴 하지만 프로그램 자체가 길지 않으므로 하나의 함수에 작성하였다.시간의 효율성을 생각해보면 큐 안의 반복문이 4번 반복하는 for문이 3개 있으므로 배열의 크기를 N이라고 할 때 약 N * N * 12번의 반복이 발생하지만 12번의 반복은 10^8이 약 1초 걸린다고 생각할 때 무시해도 될 정도의 아주 작은 시간이므로 그다지 효율성을 떨어뜨리지 않는다고 할 수 있다.
채점 결과
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [C++] 프로그래머스 외벽 점검 풀이 (0) | 2021.08.18 |
|---|---|
| [C++] 프로그래머스 매칭 점수 풀이 (0) | 2021.08.12 |
| [C++] 프로그래머스 순위 검색 풀이 (0) | 2021.08.06 |
| [C++] 프로그래머스 110 옮기기 풀이 (0) | 2021.08.06 |
| [C++] 프로그래머스 모두 0으로 만들기 풀이 (3) | 2021.08.05 |
