백준 1726 - 로봇(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1726

1726번: 로봇

BFS와 DP가 섞여있는 문제였습니다.

시작하는 좌표와 방향, 끝나는 좌표와 방향이 주어졌을때, 최소한의 명령을 해야지 도착할 수 있는지 구하는 문제입니다.

문제에서 동서남북의 방향을 정해줬기에 해당하는 값을 사용했습니다.

 

명령에는 2가지 경우가 있습니다.

1. 1~3의 값으로 이동(로봇의 방향 기준)

2. 오른쪽 or 왼쪽으로 90˚ 이동

예를 들어,  오른쪽으로 180º 이동 후, 3칸 이동하면 명령을 3번 사용한 것입니다.

 

먼저 생각해야할 것은 X방향에서 Y방향으로 바꾸는 과정에서 명령의 횟수가 다릅니다.

예를 들어, 동에서 북으로 이동한다면 1번 명령을 하면 되지만 동에서 서쪽으로 이동한다면 2번의 명령을 사용해야합니다.

그렇기에 X에서 Y방향으로 움직일 때, 몇번의 명령을 사용해야 하는지 코드로 구현해줘야 합니다.

-> turn_dir(int x, int y) 코드에서 구현되어 있습니다.

 

2번의 명령의 경우, 이동할 수 있는 횟수가 다릅니다.

1~3번의 이동을 할 수 있는데, 이동하는 동안 장애물이 있으면 안됩니다.

따라서, N번 이동할 수 있다고 했을 때, (X, Y) ~ (X+N, Y) or (X-N, Y) or (X, Y-N) or (X, Y+N) (이동방향 기준) 사이에 장애물이 있는지 확인을 해주면 됩니다

-> can_go(int x, int y, int dir, int cnt) 코드에 구현되어 있습니다.

 

마지막으로, (X, Y) 좌표에 도달한다고 했을 때, 로봇의 방향에 따라서 해당 좌표의 경우가 달라야합니다.

따라서 3차원 배열을 이용해서 해당 좌표 + 로봇의 방향으로 값을 저장해줘야 합니다.

최소 명령의 수를 구하는 문제이기 때문에 DP를 사용해 이전의 명령과 현재 좌표의 값을 계속 비교해가면서 명령의 수를 저장해줍니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

#define P pair<int,int>
#define PP pair<P, int>
#define F first
#define S second

using namespace std;

int N, M;
int map[101][101];
int check[101][101][5];
int dp[101][101][5];
int dx[5] = {0,0,0,1,-1};
int dy[5] = {0,1,-1,0,0};
PP start, finish;

int turn_dir(int x, int y){
	if(x == 1){ // 동쪽
		if(y == 1) return 0;
		else if(y == 2) return 2;
		else if(y == 3) return 1;
		else if(y == 4) return 1;
	}
	else if(x == 2){ // 서쪽
		if(y == 1) return 2;
		else if(y == 2) return 0;
		else if(y == 3) return 1;
		else if(y == 4) return 1;
	}
	else if(x == 3){ // 남쪽
		if(y == 1) return 1;
		else if(y == 2) return 1;
		else if(y == 3) return 0;
		else if(y == 4) return 2;
	}
	else if(x == 4){ // 북쪽
		if(y == 1) return 1;
		else if(y == 2) return 1;
		else if(y == 3) return 2;
		else if(y == 4) return 0;
	}
}

bool can_go(int x, int y, int dir, int cnt){
	for(int i = 1; i <= cnt; i++){
		x = x + dx[dir];
		y = y + dy[dir];
		if(map[x][y] == 1) return false;
	}
	return true;
}

void bfs(){
	queue<PP> q;
	q.push(start);
	check[start.F.F][start.F.S][start.S] = 1;
	dp[start.F.F][start.F.S][start.S] = 0;
	while(!q.empty()){
		int x = q.front().F.F;
		int y = q.front().F.S;
		int dir = q.front().S;
		q.pop();
		for(int i = 1; i <= 4; i++){
			int Add = turn_dir(dir, i);
			if(check[x][y][i] == 0 || dp[x][y][i] > dp[x][y][dir] + Add){
				check[x][y][i] = 1;
				dp[x][y][i] = dp[x][y][dir] + Add;
				q.push({{x,y}, i});
			}
			for(int j = 1; j <= 3; j++){
				int xx = x + (dx[i]*j);
				int yy = y + (dy[i]*j);
				if(xx >= 1 && xx <= N && yy >= 1 && yy <= M){
					if(!can_go(x,y,i,j)) continue;
					if(dir == i){
						if(check[xx][yy][i] == 0 || dp[xx][yy][i] > dp[x][y][dir]+1){
							check[xx][yy][i] = 1;
							dp[xx][yy][i] = dp[x][y][dir] + 1;
							q.push({{xx,yy}, i});
						}
					}
					else{
						if(check[xx][yy][i] == 0 || dp[xx][yy][i] > dp[x][y][dir]+Add+1){
							check[xx][yy][i] = 1;
							dp[xx][yy][i] = dp[x][y][dir] + Add + 1;
							q.push({{xx,yy}, i});
						}
					}
				}
			}
		}
	}
}

void solve() {
	bfs();
	cout << dp[finish.F.F][finish.F.S][finish.S];
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			cin >> map[i][j];
		}
	}	
	cin >> start.F.F >> start.F.S >> start.S;
	cin >> finish.F.F >> finish.F.S >> finish.S;
	solve();
	return 0;
}

 

 

질문 및 조언을 댓글 남겨주세요