[정올 1006] 로봇

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=285&sca=99 

JUNGOL

이런 문제처럼 좌표평면에서 상하좌우로 움직이며 조건을 체크하는 경우에는 BFS를 써야 한다.

BFS를 이용하여 목적지에 도달하는 최소 이동 횟수는 다음 절차를 따라 구현하면 된다.

1. Queue를 준비한다. Queue에 들어가는 Element는 [현재 위치(r, c), 로봇방향, 현재명령횟수] 로 구성된다.

2. 이전에 방문했던 좌표(r, c)를 재 방문한다면 최소 명령횟수로 목적지에 도달하는 게 아니게 되므로, 더 이상 체크할 필요가 없다. 이전 방문 좌표를 재 방문하지 않도록, 좌표 방문 체크용으로 지도와 동일한 2x2 배열을 만든다. (가지치기)

3. Queue에 로봇의 초기 위치와 방향에 대한 Element를 Enque한다. 위 예제에선 [(4,2), LEFT, 0] 일 것이다.

4. BFS 알고리즘으로 목적지까지의 최소 명령횟수를 구한다.

 4-1) Deque한다. 예제에선 맨 처음에 시작점인 [(4,2), LEFT, 0] 이 나올 것이다.

 4-2) Deque한 위치가 목적지인지 확인한다. 목적지라면 탈출하고 Deque한 Element의 명령횟수를 정답으로 출력한다.

 4-3) Deque한 위치와 방향을 좌표에 방문 표시한다. 좌표가 같아도 방향이 다르면 처음 방문하는 것이다.

 4-4) 현재 위치에서 다음 명령이 가능한 경우의 수를 계산한다. 

        예제 맨 처음의 경우, 다음과 같이 5가지의 경우가 나온다.

         1) Go 1 적용 시: [(4,1), LEFT, 1]  

         2) Go 2 적용 시: [(4,0), LEFT, 1]  >> 지도를 벗어나기 때문에 탈락

         3) Go 3 적용 시: [(4,-1), LEFT, 1]  >> 지도를 벗어나기 때문에 탈락

         4) Turn left 적용 시: [(4,2), DOWN, 1]

         5) Turn right 적용 시: [(4,2), UP, 1]

 4-5) 4-4)에서 불가능한 경우를 제외하고, 나머지 가능한 경우들을 Enque한다. 

        불가능한 경우는 다음과 같다.

        1) 지도 범위를 벗어나는 경우

        2) 이미 방문한 좌표와 방향인 경우 (4-3)에서 체크한 곳)

        3) 막혀 있어서 못 가는 경우 (궤도가 깔린 1 지점들)

 4-6) 4-1)로 돌아가서 반복한다.

5. 이렇게 BFS 알고리즘을 돌리면, 아래 2가지 경우로 어떻게든 탈출할 것이고, 프로그램이 종료된다.

 5-1) 목적지에 도달하는 경우 4-2)를 통해 탈출

 5-2) 모든 곳을 방문해도 목적지에 도달하지 못하는 경우 4-1)에서 Deque할 것이 없어서 탈출

 

C++ 컴파일러에서 C 스타일로 코딩하였습니다.

#include <stdio.h>

enum DIR {	ERR, EAST = 1, WEST, SOUTH, NORTH, DIRMAX	}; 
int grid[105][105], R, C, s, e;
int checked[105][105]; //각 위치에서 각 방향에 선 적이 있는 지 확인함, EAST(2), WEST(4), SOUTH(8), NORHT(16)
int dr[DIRMAX] = { 0,0,0,1,-1 }, dc[DIRMAX] = { 0,1,-1,0,0 };
int checkval[DIRMAX] = {0, 2, 4, 8, 16};
DIR turnL[DIRMAX] = { ERR,NORTH,SOUTH,EAST,WEST };
DIR turnR[DIRMAX] = {ERR,SOUTH,NORTH,WEST,EAST};
const char* debug[DIRMAX] = {"", "동", "서", "남", "북"};

//좌회전, 우회전, 앞1, 앞2, 앞3 갈 수 있음
struct P {
	int r, c, cnt;
	DIR dir;
	bool operator==(P& cmp) {
		if (r == cmp.r && c == cmp.c && dir == cmp.dir) return true;
		else return false;
	}
} que[50000], DST, SRC; //Queue 구현

void enq(int r, int c, DIR dir, int cnt) {
	que[e].r = r, que[e].c = c, que[e].dir = dir, que[e++].cnt = cnt;
	checked[r][c] += checkval[dir];
}
P deq() { return que[s++]; }

bool check(int r, int c, DIR dir) {
	if (r < 1 || c < 1 || r > R || c > C) return false;
	if (checked[r][c] & checkval[dir]) return false; //이미 먼저 갔던 곳이면 못 간다
	else return true;
}

bool goalin(P& src, P& dst) {
	if (src.dir == dst.dir) { //go 인 경우, pp->np로 이동할 때, 도착지까지 가는 길에 1이 하나라도 있으면, Enque하면 안 됨
		int s, e;
		if (src.r == dst.r) {
			if (src.c > dst.c) s = dst.c, e = src.c;
			else s = src.c, e = dst.c;
			for (int i = s; i <= e; i++) 
				if (grid[src.r][i]) return false;
		}
		else {
			if (src.r > dst.r) s = dst.r, e = src.r;
			else s = src.r, e = dst.r;
			for (int i = s; i <= e; i++) 
				if (grid[i][src.c]) return false;
		}
	}
	if (DST == dst) return true; //목적지 도착
	if (check(dst.r, dst.c, dst.dir)) { 
		enq(dst.r, dst.c, dst.dir, dst.cnt + 1); 
	} //목적지 도착이 아닌 경우 enque
	return false;
}

int bfs() {
	enq(SRC.r, SRC.c, SRC.dir, 1);
	P cur, tmp;
	while (s < e) {
		tmp = cur = deq();
		for (int go = 3; go > 0; go--) { //go 3,2,1 차례대로 확인, 가는길에 1이 있으면 안 됨
			tmp.r = cur.r + go * dr[cur.dir];
			tmp.c = cur.c + go * dc[cur.dir];
			if (goalin(cur, tmp)) return tmp.cnt; //목적지 도착
		}
		tmp = cur; //좌 확인
		tmp.dir = turnL[tmp.dir];
		if (goalin(cur, tmp)) return tmp.cnt; //목적지 도착
		tmp = cur; //우 확인
		tmp.dir = turnR[tmp.dir];
		if (goalin(cur, tmp)) return tmp.cnt; //목적지 도착
	}
}

int main(void) {
	//freopen("input.txt", "r", stdin);
	scanf("%d%d", &R, &C);
	for (int r = 1; r <= R; r++)
		for (int c = 1; c <= C; c++) scanf("%d", &grid[r][c]);
	scanf("%d%d%d", &SRC.r, &SRC.c, &SRC.dir);
	scanf("%d%d%d", &DST.r, &DST.c, &DST.dir);
	printf("%d\n", bfs());
	return 0;
}