[백준 1726] 로봇

https://www.acmicpc.net/problem/1726

1726번: 로봇

 

이전에 짰던 코드는 다음과 같다.

#include <cstdio>
#include <queue>
#include <algorithm>
int M, N;	// 행, 열
int board[100 + 2][100 + 2];
int visited[100 + 2][100 + 2][4 + 2];	// (x, y)에서 dir 4방향 
int rx, ry, rd;		// 현재 로봇 위치 방향 
int ex, ey, ed;		// 목적 위치, 방향

struct _st
{
	int x, y;	// 현재 위치
	int dir;	// 방향
	int cnt;	// 움직인 횟수
};

std::queue<_st> Q;

// 0북 1동 2서 3남
int dir_x[4] = { -1, 0, 0, 1 };
int dir_y[4] = { 0, 1, -1, 0 };
// 오른쪽으로 회전 : 동 남 북 서
int right[4] = { 1, 3, 0, 2 };
// 왼쪽으로 회전 : 서 북 남 동
int left[4] = { 2, 0, 3, 1 };



void input()
{
	scanf("%d %d", &M, &N);
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &board[i][j]);
		}
	}
	scanf("%d %d %d", &rx, &ry, &rd);
	rd %= 4;
	scanf("%d %d %d", &ex, &ey, &ed);
	ed %= 4;
}


bool go_chk(int x, int y, int dir, int cmd)
{
	for (int s = 1; s <= cmd; s++) {
		int nx = x + s * dir_x[dir];
		int ny = y + s * dir_y[dir];

		if (nx < 1 || nx > M || ny < 1 || ny > N) return false;
		if (board[nx][ny]) return false;	// Go 1, 2, 3 모두 벽을 뚫고 지나가면 안됨	
											// 가는 길에 벽이 있으면 뚫고 지나갈 수 없음 
		if (s == cmd && visited[nx][ny][dir]) return false;		// 갈 곳을 이미 방문했다면 안가도 됨 
	}
	return true;
}



int BFS()
{
	visited[rx][ry][rd] = 1;		// 현재 위치 밑 방향 방문 처리
	Q.push({ rx, ry, rd, 0 });		// 현재 로봇의 위치와 방향

	while (!Q.empty()) {
		_st data = Q.front();
		//printf("(%d %d) dir %d cnt %d\n", data.x, data.y, data.dir, data.cnt);
		Q.pop();

		if (data.x == ex && data.y == ey && data.dir == ed) return data.cnt;

		//Go 1, 2, 3
		int nx = 0, ny = 0, nd = 0;
		for (int cmd = 1; cmd <= 3; cmd++) {
			if (go_chk(data.x, data.y, data.dir, cmd)) {	// 벽을 뚫고 갈 수 없기 때문에 가는 길을 모두 확인해야 한다. 
				nx = data.x + cmd * dir_x[data.dir];
				ny = data.y + cmd * dir_y[data.dir];
				visited[nx][ny][data.dir] = 1;
				Q.push({ nx, ny, data.dir, data.cnt + 1 });		// 방향은 바꾸지 않고 전진만 한다. 
			}
		}

		// Turn left, right
		for (int cmd = 0; cmd < 2; cmd++) {
			switch (cmd)
			{
			case 0:
				nd = left[data.dir];
				break;
			case 1:
				nd = right[data.dir];
				break;
			}
			if (visited[data.x][data.y][nd]) continue;
			visited[data.x][data.y][nd] = 1;
			Q.push({ data.x, data.y, nd, data.cnt + 1 });
		}
	}
}


int main()
{
	input();
	int ans = BFS();
	printf("%d\n", ans);
	return 0;
}

 

 

++ 22.10.19  새로 짠 코드 

#include <cstdio>
#include <queue>
int M, N;	// 행, 열
int board[100 + 2][100 + 2];
int visited[100 + 2][100 + 2][5];	// 동1, 서2, 남3, 북4 

struct _st
{
	int x, y;
	int dir;
};

_st Start[1];
_st Target[1];
std::queue<_st> Q;

// 동1, 서2, 남3, 북4
int dir_x[5] = { 0, 0, 0, 1, -1 };
int dir_y[5] = { 0, 1, -1, 0, 0 };
// 북, 남, 동, 서
int left[5] = { 0, 4, 3, 1, 2 };
// 남. 북, 서, 동
int right[5] = { 0, 3, 4, 2, 1 };


void input()
{
	scanf("%d %d ", &M, &N);
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &board[i][j]);
		}
	}
	scanf("%d %d %d", &Start[0].x, &Start[0].y, &Start[0].dir);		// 초기상태 
	scanf("%d %d %d", &Target[0].x, &Target[0].y, &Target[0].dir);		// 목적상태 
}


void init()
{
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= N; j++) {
			for (int p = 1; p <= 4; p++) {
				visited[i][j][p] = -1;
			}
		}
	}
}


bool chk(int x, int y, int dir, int k)
{
	for (int i = 1; i <= k; i++) {
		int nx = x + i * dir_x[dir];
		int ny = y + i * dir_y[dir];

		if (nx < 1 || nx > M || ny < 1 || ny > N) return false;
		if (board[nx][ny] == 1) return false;
	}
	return true;
}



int BFS()
{
	
	init();
	
	Q.push({ Start[0].x, Start[0].y, Start[0].dir });
	visited[Start[0].x][Start[0].y][Start[0].dir] = 0;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		if (data.x == Target[0].x && data.y == Target[0].y && data.dir == Target[0].dir) return visited[data.x][data.y][data.dir];

		// Go k
		for (int k = 1; k <= 3; k++) {
			int nx = data.x + k * dir_x[data.dir];
			int ny = data.y + k * dir_y[data.dir];

			if (nx < 1 || nx > M || ny < 1 || ny > N) continue;
			if (!chk(data.x, data.y, data.dir, k)) continue;
			if (visited[nx][ny][data.dir] > 0) continue;
			Q.push({ nx, ny, data.dir });
			visited[nx][ny][data.dir] = visited[data.x][data.y][data.dir] + 1;
		}
		// Trun dir
		int ldir = left[data.dir];
		if (visited[data.x][data.y][ldir] == -1) {
			Q.push({ data.x, data.y, ldir });
			visited[data.x][data.y][ldir] = visited[data.x][data.y][data.dir] + 1;
		}
		int rdir = right[data.dir];
		if (visited[data.x][data.y][rdir] == -1) {
			Q.push({ data.x, data.y, rdir });
			visited[data.x][data.y][rdir] = visited[data.x][data.y][data.dir] + 1;
		}
	}
	return -1;
}



int main()
{
	input();
	int ans = BFS();
	printf("%d\n", ans);
	return 0;
}

 

BFS 문제이다. 

 

1. 3차원 방문 배열을 사용하는 이유는 "상태"를 저장하기 위함이다.

같은 좌표에 있더라도 어느 방향을 바라보는가에 따라 결과가 달라지기 때문에, 서로 다른 상태라고 볼 수 있다. 

 

2. 큐가 비어지기 전, 목적지의 좌표와 방향을 만나면 바로 함수를 종료해준다. 

목적 상태가 되기 위한 optimal choice 이기 때문이다. 큐가 끝나고 나서 chk 배열을 리턴해주는 경우는, 목적 상태까지 다다르는 각각의 cost가 달라서 모든 가짓수를 다 시도해보아야 하는 경우이다. 

 

3. 벽을 뚫고 지나갈 수 없다. 

따라서 1, 2, 3만큼 움직일 때 가는 길목에 벽이 있는지 없는지 모두 확인을 해주어야 한다. (8% 에러인 경우 벽을 뚫고 지나가고 있지는 않은지 확인해보자)

 

 

=> 이거 풀고 "1938 통나무 옮기기" 문제 추천.. 슷비슷비