[C++/프로그래머스] 블록 이동하기

문제 설명

로봇개발자 무지는 한 달 앞으로 다가온 카카오배 로봇경진대회에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 무지는 0과 1로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 0은 빈칸을 1은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다.

로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1, 2), (1, 3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2, 1), (2, 2) 두 칸을 차지하게 됩니다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.

로봇은 다음과 같이 조건에 따라 회전이 가능합니다.

위 그림과 같이 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다.

0과 1로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.

제한사항

• board의 한 변의 길이는 5 이상 100 이하입니다.
• board의 원소는 0 또는 1입니다.
• 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

입출력 예

board	result
[[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

문제에 주어진 예시와 같습니다.
로봇이 오른쪽으로 한 칸 이동 후, (1, 3) 칸을 축으로 반시계 방향으로 90도 회전합니다. 다시, 아래쪽으로 3칸 이동하면 로봇은 (4, 3), (5, 3) 두 칸을 차지하게 됩니다. 이제 (5, 3)을 축으로 시계 방향으로 90도 회전 후, 오른쪽으로 한 칸 이동하면 (N, N)에 도착합니다. 따라서 목적지에 도달하기까지 최소 7초가 걸립니다.

 

풀이

풀면서 느낀 주의사항

1. 로봇은 현재 놓여있는 방향에 관계없이 상하좌우로 움직일 수 있다.

처음에 가로로 놓여있으면 좌,우, 세로로 놓여있으면 위,아래 로만 움직일 수 있는줄 알고 코딩을 진행했다. 하지만 로봇은 언제든지 (벽만 없으면) 상하좌우로 모두 움직일 수 있다! 

 

2. 회전할 때 축에 따른 경우의 수 나뉨.

예를들어 로봇이 세로방향 일 때, 왼/오 두 가지로 회전가능하다고 생각하기 쉽지만, 어느 칸이 축이 되느냐에 따라 경우의 수가 나뉜다는 것을 알 수 있다. 

따라서, 위 칸이 축 - 왼/오, 아래 칸이 축 - 왼/오 -> 4가지로 나뉜다.

로봇이 가로방향일 때도 마찬가지로 적용된다. 

 

3. 처음부터 너무 어렵게 생각하지 말기

로봇이 2칸을 차지하고, 심지어 회전까지 들어가보여서 매우 어렵게 보였다. (실제로 어렵기도 했지만..) 하지만 bfs를 조금 변형하면 풀 수 있는 문제였다. 조건이 많다고 처음부터 겁먹을 필요는 없을 것 같다.

 

내용

1. 로봇 구조체(struct) 이용

• time
  • 로봇이 해당 위치로 올 때 까지 걸린 시간
• x, y 
  • 로봇의 좌표, 로봇이 가로와 세로일 때 각각 아래 사진속 칸을 x,y로 설정

• type 
  • 가로 = 0, 세로 = 1

2. bfs 이용

종료 조건을 만족할 때 까지 큐에서 하나를 꺼내고,  해당 위치에서 가능한 다음 위치들을 모두 넣는 방식으로 진행

종료 조건 : 로봇이 (n-1,n-1)에 위치했을 때. 

코드

처음에 bfs로 풀어야지 하다가, 코드를 다 짜고보니 dfs로 풀고 있었다는 사실을 깨달았다.. 처음부터 다시 시작..

#include <string>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
struct robot {
	int time;
	int x;
	int y;
	int type; // 0 : 가로, 1 : 세로
};
bool check(int x, int y, int type);
int visit[101][101][2]; // 0 : 가로, 1 : 세로
int dx[] = { -1, 1, 0, 0 }; //상 하 좌 우
int dy[] = { 0, 0, -1, 1 };
vector<vector<int> > table;


bool check(int x, int y, int type) { // 범위를 벗어나거나, 벽에 부딪히면 false
	int N = table.size();
	if (type == 0) {//가로
		if (x < 0 || y < 0 || x >= N || y + 1 >= N) return false;
		if (table[x][y] || table[x][y + 1]) return false;
	}
	else {//세로
		if (x < 0 || y < 0 || x + 1 >= N || y >= N) return false;
		if (table[x][y] || table[x + 1][y]) return false;
	}
	return true;
}
int solution(vector<vector<int>> board) {
	int answer = 0, N = board.size(); 
	table = board;

	memset(visit, 0, sizeof(visit));

	queue<robot> q;
	q.push({ 0, 0, 0, 0 });
	while (!q.empty()) {
		robot now = q.front(); 
		q.pop();
		if ((now.type == 0 && now.x == N - 1 && now.y == N - 2) || (now.type == 1 && now.x == N - 2 && now.y == N - 1)) {
			return now.time;
		}

		for (int i = 0; i < 4; i++) { // 상하좌우 이동
			int nx = now.x + dx[i];
			int ny = now.y + dy[i];
			if (!check(nx, ny, now.type) || visit[nx][ny][now.type]) continue; //이전에 방문한 적 있으면 건너뛰기
			visit[nx][ny][now.type] = 1;
			q.push({ now.time + 1, nx, ny, now.type });
		}

		//여기부터 회전
		if (now.type == 0) { //가로
			//오른쪽 칸이 축
			if (now.x + 1 <= N - 1 && !table[now.x + 1][now.y] && !table[now.x + 1][now.y + 1] && !visit[now.x][now.y + 1][1]) {
				q.push({ now.time + 1, now.x, now.y + 1, 1 });
			}
			if (now.x - 1 >= 0 && !table[now.x - 1][now.y] && !table[now.x - 1][now.y + 1] && !visit[now.x - 1][now.y + 1][1]) {
				q.push({ now.time + 1, now.x - 1, now.y + 1, 1 });
			}
			//왼쪽 칸이 축
			if (now.x + 1 <= N - 1 && !table[now.x + 1][now.y + 1] && !table[now.x + 1][now.y] && !visit[now.x][now.y][1]) {
				q.push({ now.time + 1, now.x, now.y, 1 });
			}
			if (now.x - 1 >= 0 && !table[now.x - 1][now.y + 1] && !table[now.x - 1][now.y] && !visit[now.x - 1][now.y][1]) {
				q.push({ now.time + 1, now.x - 1, now.y, 1 });
			}
		}
		else { //세로
		    //아래칸이 축
			if (now.y - 1 >= 0 && !table[now.x][now.y - 1] && !table[now.x + 1][now.y - 1] && !visit[now.x + 1][now.y - 1][0]) {
				q.push({ now.time + 1, now.x + 1, now.y - 1, 0 });
			}
			if (now.y + 1 <= N - 1 && !table[now.x][now.y + 1] && !table[now.x + 1][now.y + 1] && !visit[now.x + 1][now.y][0]) {
				q.push({ now.time + 1, now.x + 1, now.y, 0 });
			}
			//위 칸이 축
			if (now.y - 1 >= 0 && !table[now.x + 1][now.y - 1] && !table[now.x][now.y - 1] && !visit[now.x][now.y - 1][0]) {
				q.push({ now.time + 1, now.x, now.y - 1, 0 });
			}
			if (now.y + 1 <= N - 1 && !table[now.x + 1][now.y + 1] && !table[now.x][now.y + 1] && !visit[now.x][now.y][0]) {
				q.push({ now.time + 1, now.x, now.y, 0 });
			}
		}
	}
}