[BOJ1726] 로봇

[BOJ1726] 로봇

문제 링크

문제 설명

• 보드판은 0과 1로 이루어져있다. 0은 로봇이 지나갈 수 있는 곳, 1은 로봇이 지나갈 수 없는 곳이다.
• 로봇은 동서남북 네방향 중 한 곳으로 방향을 가지고 있다.
• 로봇에게 내릴 수 있는 명령은 2가지가 있다.
  1. 향하고 있는 방향으로 1,2,3 만큼 이동하게 하는 명령
  2. 방향을 회전시키는 명령(왼쪽,오른쪽으로 명령 한번 당 90도씩 움직일 수 있다.)
• 보드판과 로봇의 시작좌표, 방향, 로봇의 도착좌표, 방향이 입력으로 주어질 때, 로봇이 이동하여 도착좌표에 도착하고, 방향또한 도착방향과 같을 때까지 로봇에게 내린 명령의 최소 횟수를 출력하는 문제이다.

코드리뷰

• BFS를 통해 check배열의 해당 좌표까지의 최소 명령횟수를 계속해서 저장해 나간다.
• 방향에 대해서는 왼쪽, 오른쪽 구분없이 다음 방향이 내 방향의 정반대 방향일 경우 명령어 수가 +2 된다. 다음 방향이 내 양옆의 90도 방향일 경우 최소 횟수는 왼쪽일 땐 왼쪽 한번, 오른쪽일 땐 오른쪽 한번이므로 명령어수를 +1 해주면 된다.
• 방향에 대한 명령어 수가 정해지면, 그 방향으로 갈 수 있는 거리 역시 1이든 2이든 3이든 명령어수는 +1이 된다.
• 최종 도착좌표에 BFS 탐색을 통해 도착하였을 경우, 그 방향과 입력으로 받은 방향이 같을 경우는 그대로 답의 후보가 되고, 180도 반대일 경우 +2가 답의 후보가 되고, 90도 옆에 있는 방향일 경우 +1이 답의 후보가 된다.
• 코드를 짜다보니 맘에들지 않게 지저분하게 짜게된 것 같다. 코드짜는 시간을 줄이면서도 코드도 클린하게 짜려고 노력해봐야겠다.

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

typedef struct {
	int m;
	int n;
	int dir;
	int cnt;
}Queue;

int N, M;
int board[101][101];
int min_check[101][101];
int dc[4] = { 0,0,1,-1 };
int dr[4] = { 1,-1,0,0 };
int endm, endn, endd;
int ans = 1000000000;
queue <Queue> q;

void bfs() {
	while (!q.empty()) {
		int m = q.front().m;
		int n = q.front().n;
		int dir = q.front().dir;
		int cnt = q.front().cnt;
		if (m == endm && n == endn) { //답의 후보를 찾는 부분
			if (dir == endd) {
				ans = min(ans, cnt);
			}
			else {
				if ((dir == 1 && endd == 2) || (dir == 2 && endd == 1) || (dir == 3 && endd == 4) || (dir == 4 && endd == 3)) {
					ans = min(ans, cnt + 2);
				}
				else {
					ans = min(ans, cnt + 1);
				}
			}
		}
		q.pop();
		for (int d = 0; d < 4; d++) {
			for (int k = 1; k <= 3; k++) {
				int mnext = m + k * dc[d];
				int nnext = n + k * dr[d];
				if (mnext < 1 || mnext > M || nnext < 1 || nnext > N) break;
				else if (board[mnext][nnext] == 1) break;
				else { // 다음 좌표로 이동시 그 좌표까지의 명령어 수 push하는 부분
					if(dir!=d+1){
						if ((dir == 1 && d+1 == 2) || (dir == 2 && d+1 == 1) || (dir == 3 && d+1 == 4) || (dir == 4 && d+1 == 3)) {
							if (min_check[mnext][nnext] == 0 || min_check[mnext][nnext] > cnt + 3) {
								min_check[mnext][nnext] = cnt + 3;
								q.push({ mnext,nnext,d+1,cnt + 3 });
							}
						}
						else {
							if (min_check[mnext][nnext] == 0 || min_check[mnext][nnext] > cnt + 2) {
								min_check[mnext][nnext] = cnt + 2;
								q.push({ mnext,nnext,d+1,cnt + 2 });
							}
						}
					}
					else {
						if (min_check[mnext][nnext] == 0 || min_check[mnext][nnext] > cnt + 1) {
							min_check[mnext][nnext] = cnt + 1;
							q.push({ mnext,nnext,d+1,cnt + 1 });
						}
					}
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> M >> N;
	for (int m = 1; m <= M; m++) {
		for (int n = 1; n <= N; n++) {
			cin >> board[m][n];
		}
	}
	int startm, startn, startd;
	cin >> startm >> startn >> startd;
	cin >> endm >> endn >> endd;
	q.push({ startm,startn,startd,0});
	min_check[startm][startn] = q.front().cnt;
	bfs();
	cout << ans << '\n';
	return 0;
}