[백준 1726] 로봇

분류 : bfs

 

요구사항

명령을 최소로 하여 start 지점에서 end 지점까지 이동하기

 

풀이

bfs문제 인데 visit 배열을 2개를 사용하였다

하나는 1~3까지 이동하는 visit배열이고, 하나는 현재 칸에서 회전하는 visit배열이다

주의 할점

현재 방향이 1이라면 180도 이동하였을때는 cnt가 2증가한다

그리고 q가 빌때까지 돌려줘야 하는것이다

바로 출력하면 최소가 아닌 답을 출력한다

 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

struct go {
	int x;
	int y;
	int dir;
	int cnt;
};
int n, m;
int sr, sc, sdir;
int er, ec, edir;
int map[110][110];
int visit[110][110][10][10];
int ans = 987654321;
int dr[5] = { 0,0,0,1,-1 };
int dc[5] = { 0,1,-1,0,0 };
int visitdir[110][110][10];
void bfs() {
	queue<go> q;
	q.push({ sr,sc,sdir,0 });
	visit[sr][sc][sdir][0] = 1;
	visitdir[sr][sc][sdir] = 1;
	int ccnt = 0;
	while(!q.empty()) {
		ccnt++;
		//if (ccnt > 50) break;
		int r = q.front().x;
		int c = q.front().y;
		int cnt = q.front().cnt;
		int dir = q.front().dir;
	//	cout << "R" << r << "C" << c << "dir" << dir << "cnt" << cnt << endl;
		q.pop();
		if (r == er && c == ec && dir == edir) {
			ans = min(ans, cnt);
			continue;
		}
		//현재 방향으로 3칸 이동하기
		for (int i = 1; i <= 3; i++) {
			int nr = r + i*dr[dir];
			int nc = c + i*dc[dir];
			if (nr<1 || nc< 1 || nr>n || nc>m) break;
			if (map[nr][nc] == 1) break;
			if (map[nr][nc] == 0) {
				if (visit[nr][nc][dir][i] == 0) {
				//	cout << "C" << nr<<" "<<nc<<i<<endl;
					visit[nr][nc][dir][i] = 1;
					q.push({ nr,nc,dir,cnt + 1 });
				}
			}
		}
		//내방향 제외하고 4방향으로 돌아보기
		for (int i = 1; i <= 4; i++) {
			int temp;
			int ncnt;
			if (i == dir) { visitdir[r][c][i] = 1; continue; }
			if (dir == 1) {
				if (i == 1) continue;
				else if (i == 2) ncnt = cnt + 2;
				else if (i == 3) ncnt = cnt + 1;
				else if (i == 4) ncnt = cnt + 1;
				
			}
			else if (dir == 2) {
				if (i == 1) ncnt = cnt + 2;
				else if (i == 2) continue;
				else if (i == 3) ncnt = cnt + 1;
				else if (i == 4) ncnt = cnt + 1;
			}
			else if (dir == 3) {
				if (i == 1) ncnt = cnt + 1;
				else if (i == 2) ncnt = cnt + 1;
				else if (i == 3) continue;
				else if (i == 4) ncnt = cnt + 2;
			}
			else if (dir == 4) {
				if (i == 1) ncnt = cnt + 1;
				else if (i == 2) ncnt = cnt + 1;
				else if (i == 3) ncnt = cnt + 2;
				else if (i == 4) continue;
			}
			if (visitdir[r][c][i] == 0) {
				visitdir[r][c][i] == 1;
			//	cout << "B" << r << " " << c << i << endl;
				q.push({ r,c,i,ncnt });
			}
		}
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	scanf("%d%d%d", &sr, &sc, &sdir);
	scanf("%d%d%d", &er, &ec, &edir);
	bfs();
	cout << ans << endl;
}