글 읽기 - 13460 구슬탈출 질문드려요.

junoko91 5년 전 0

일단 전략 자체는 재귀로 접근하였고

1.맵을 매개변수를 전달한다.

2.이동가능한 방향을 찾는다.

3.직전에 이동한 방향이거나 직전 이동방향의 반대방향은 다음 이동방향에서 제외한다.

4.실패조건에 따른 재귀함수 return.

5.성공조건 달성시 시도횟수 갱신후 return.

이정도 입니다.

예제는 모두 맞추었고 이외의 문제점을 도저히 못찾겠습니다.

소스 리뷰는 계속 하였는데 도저히 알고리즘적인 문제를 찾지 못하겠습니다.

저의 접근 방법이나 소스적인 문제가 있으면 문제점을 찾아주시면 고맙겠습니다.

분석하기 편하시라고 주석은 달아놨고 분석하는데 크게 어렵지 않을꺼라 생각됩니다.

맨위 DEBUG true면 이동전 맵상태와 이동후 맵상태를 출력합니다.

#include <iostream>
#include <vector>
#include <algorithm>

#define DEBUG true
//#define DEBUG false

using namespace std;

int Min = 1000;

typedef struct cordinate {
	int x;
	int y;
}Cordinate;

class Direction {
public:
	bool flag[4];

	Direction() {
		for (int i = 0; i < 4; i++) {
			flag[i] = false;
		}
	}
};

typedef vector<vector<char>> t_map;

class Map {
public:
	bool blueFlag = false;
	bool redFlag = false;
	t_map map;
	Cordinate cord_red, cord_blue;

	Map() {};
	Map(t_map map, Cordinate r, Cordinate b) {
		this->map = map;
		this->cord_red = r;
		this->cord_blue = b;
	}
};

//주변에 벽을 체크하여 R,B 둘 중 한 구슬만 움직일 수 있어도 되는 방향들을 체크
Direction checkDir(Map &map, int rx, int ry, int bx, int by) {
	Direction ret;
	//x--,y++,x++,y--  순서
	//LEFT,UP,RIGHT,DOWN 순서
	if (map.map[rx - 1][ry] != '#') { ret.flag[0] = true; }
	if (map.map[rx][ry + 1] != '#') { ret.flag[1] = true; }
	if (map.map[rx + 1][ry] != '#') { ret.flag[2] = true; }
	if (map.map[rx][ry - 1] != '#') { ret.flag[3] = true; }

	if (map.map[bx - 1][by] != '#') { ret.flag[0] = true; }
	if (map.map[bx][by + 1] != '#') { ret.flag[1] = true; }
	if (map.map[bx + 1][by] != '#') { ret.flag[2] = true; }
	if (map.map[bx][by - 1] != '#') { ret.flag[3] = true; }

	return ret;
}

void swap(char &a, char &b) {
	char tmp = a;
	a = b;
	b = tmp;
}

//x--,y++,x++,y--  순서
//LEFT,UP,RIGHT,DOWN 순서
int dirDx(int dir) {
	if (dir == 0)
		return -1;
	if (dir == 2)
		return 1;
	return 0;
}

int dirDy(int dir) {
	if (dir == 1)
		return 1;
	if (dir == 3)
		return -1;
	return 0;
}

//상황에 따른 Red가 먼저 움직여도 되는지 판단.
bool checkOrder(int dir, Cordinate red, Cordinate blue) {
	switch (dir) {
	case 0:
		if (red.x < blue.x)
			return true;
		else
			return false;
	case 1:
		if (red.y > blue.y)
			return true;
		else
			return false;
	case 2:
		if (red.x > blue.x)
			return true;
		else
			return false;
	case 3:
		if (red.y < blue.y)
			return true;
		else
			return false;
	}
}

//x--,y++,x++,y--  순서
//LEFT,UP,RIGHT,DOWN 순서
Map move(Map map, int dir) {
	Cordinate original_cord_red = map.cord_red;
	Cordinate original_cord_blue = map.cord_blue;
	int dx = dirDx(dir);
	int dy = dirDy(dir);
	int isRedFirst = checkOrder(dir, map.cord_red, map.cord_blue);

	if (isRedFirst) {
		while (true) {
			map.cord_red.x += dx;
			map.cord_red.y += dy;

			if (map.map[map.cord_red.x][map.cord_red.y] != '.') {
				if (map.map[map.cord_red.x][map.cord_red.y] == 'O') {
					map.map[original_cord_red.x][original_cord_red.y] = '.';
					map.redFlag = true;
					break;
				}
				else {
					map.cord_red.x -= dx;
					map.cord_red.y -= dy;
					swap(map.map[map.cord_red.x][map.cord_red.y], map.map[original_cord_red.x][original_cord_red.y]);
					break;
				}
			}
		}
		while (true) {
			map.cord_blue.x += dx;
			map.cord_blue.y += dy;

			if (map.map[map.cord_blue.x][map.cord_blue.y] != '.') {
				if (map.map[map.cord_blue.x][map.cord_blue.y] == 'O') {
					map.blueFlag = true;
					return map;
				}
				else {
					map.cord_blue.x -= dx;
					map.cord_blue.y -= dy;
					swap(map.map[map.cord_blue.x][map.cord_blue.y], map.map[original_cord_blue.x][original_cord_blue.y]);
					return map;
				}
			}
		}
	}
	else {
		while (true) {
			map.cord_blue.x += dx;
			map.cord_blue.y += dy;

			if (map.map[map.cord_blue.x][map.cord_blue.y] != '.') {
				if (map.map[map.cord_blue.x][map.cord_blue.y] == 'O') {
					map.blueFlag = true;
					return map;
				}
				else {
					map.cord_blue.x -= dx;
					map.cord_blue.y -= dy;
					swap(map.map[map.cord_blue.x][map.cord_blue.y], map.map[original_cord_blue.x][original_cord_blue.y]);
					break;
				}
			}
		}
		while (true) {
			map.cord_red.x += dx;
			map.cord_red.y += dy;

			if (map.map[map.cord_red.x][map.cord_red.y] != '.') {
				if (map.map[map.cord_red.x][map.cord_red.y] == 'O') {
					map.map[original_cord_red.x][original_cord_red.y] = '.';
					map.redFlag = true;
					return map;
				}
				else {
					map.cord_red.x -= dx;
					map.cord_red.y -= dy;
					swap(map.map[map.cord_red.x][map.cord_red.y], map.map[original_cord_red.x][original_cord_red.y]);
					return map;
				}
			}
		}
	}
}

//이전방향 반대방향 계산
//x--,y++,x++,y--  순서
//LEFT,UP,RIGHT,DOWN 순서
int reverseDir(int dir) {
	switch (dir) {
	case 0:
		return 2;
	case 1:
		return 3;
	case 2:
		return 0;
	case 3:
		return 1;
	}
}

void printMap(Map &map) {
	printf("\n");
	for (int i = 0; i < map.map.size(); i++) {
		for (int j = 0; j < map.map[i].size(); j++) {
			printf("%c", map.map[i][j]);
		}
		printf("\n");
	}
}

void solve(Map map, int lastDir, int count) {
	//이동횟수가 10번이 넘거나 이미 성공한 횟수보다 많은 시도를 하는경우 return
	if (count > 10 || Min <= count) {
		return;
	}

	int revDir = reverseDir(lastDir);
	Direction dir = checkDir(map, map.cord_red.x, map.cord_red.y, map.cord_blue.x, map.cord_blue.y);

	for (int i = 0; i < 4; i++){
		//이전 방향, 반대방향, 가능하지 않은 방향은 패스
		if (i == revDir || i == lastDir) { continue; }
		if (dir.flag[i] == false) { continue; }

		if (DEBUG) {
			//이동 전 맵 출력
			system("cls");
			printMap(map);
		}

		//이동 후 새로운 맵
		Map tmpMap(move(map, i));

		if (DEBUG) {
			//이동 후 맵 출력
			printMap(tmpMap);
			cout << count << endl;
		}

		// 파란구슬이 홀에 들어간경우 return
		if (tmpMap.blueFlag) continue;
		// 빨간구슬만 홀에 들어간경우 시도값 갱신
		if (tmpMap.redFlag && !tmpMap.blueFlag) {
			Min = min(Min, count);
			continue;
		}
        
        //가능한 방향으로 이동 된 맵을 다시 재귀호출
		solve(tmpMap, i, count + 1);
	}
	return;
}

int main(void) {
	int N, M;

	cin >> N >> M;

	//2차원 벡터
	t_map inputArray(N);

	Cordinate r, b;

	char tmp;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> tmp;
			if (tmp == 'R') {
				r.x = i;
				r.y = j;
			}

			if (tmp == 'B') {
				b.x = i;
				b.y = j;
			}
			inputArray[i].push_back(tmp);
		}
	}

	Map map(inputArray, r, b);

	solve(map, -1, 1);

	if (Min <= 10)
		cout << Min;
	else
		cout << "-1";

	return 0;
}

djm03178 5년 전 1

https://www.acmicpc.net/board/...

여기에 틀리는 예시들이 있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

13460 구슬탈출 질문드려요.

junoko91 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말