글 읽기 - (구슬탈출2)예외케이스를 찾긴 했는데, 이 케이스가 왜 이런 답인지 모르겠습니다.

wjd5126 1년 전 1

해당 예외케이스가 있는 글

케이스 :

8 10

##########
#.......O#
###.#.#.##
#........#
#B#.###..#
##.....#.#
#R...#...#
##########
ans: 10

우선 제가 눈으로 계산했을 때,

1. 오른쪽

2. 위

3. 오른

4. 아래

5. 오른

6. 위

7. 오른

8. 위

9. 왼

10. 위

11. 오른

으로 11번의 계산이 필요하다고 이해했습니다.

진짜 게시판 다뒤져서 예외케이스로 이거 하나 찾았는데 막상 눈으로 해보니깐 제 코드랑 같은 결과가 나와서 제가 틀렸고, 잘못이해한 제가 잘못된 코드를 짠건지 / 케이스가 잘못된건지 / 그냥 멍청한건지 궁금해서 질문드립니다...

코드는 간단하게 리뷰하면 find_bfs에서 bfs로 가야할 방향 찾고 + go를 통해 직진합니다. 데이터는 구조체 marble을 통해 blue와 red위치 전부 저장합니다.

조언 감사합니다!

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
struct hole {
	int y;
	int x;
};
struct marble {
	int ry;
	int rx;
	int by;
	int bx;
	int time = 0;
};

/*
문제의 케이스 박제
8 10

##########
#.......O#
###.#.#.##
#........#
#B#.###..#
##.....#.#
#R...#...#
##########
ans: 10

*/
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int bx, by;
char map[12][12] = { 0 };
char visualmap[12][12] = { 0 }; //테스트용
int visited[12][12][12][12] = { 0 };
marble o;
hole a;
int mintime = 1000;

//테스트용
void print() {
	for (int i = 0; i < by; i++) {
		for (int j = 0; j < bx; j++) {
			cout << visualmap[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n"; cout << "\n"; cout << "\n"; cout << "\n";
}

void input() {
	cin >> by >> bx;
	for (int i = 0; i < by; i++) {
		for (int j = 0; j < bx; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'R') {
				o.rx = j;
				o.ry = i;
				map[i][j] = '.';
			}
			if (map[i][j] == 'B') {
				o.bx = j;
				o.by = i;
				map[i][j] = '.';
			}
			if (map[i][j] == 'O') {
				a.x = j;
				a.y = i;
			}
		}
	}
	copy(&map[0][0], &map[0][0] + (12 * 12), &visualmap[0][0]);
}

marble go(marble arr, int dir) {
	marble nmarble = arr;
	int breaker = 0;
	int check[2] = { 0,0 };
	while (1) {
		//red때문에 go에 왔는데 blue의 위치가 벽일 경우 혹은 반대
		if (map[nmarble.ry][nmarble.rx] == '#')check[0] = 2;
		if (map[nmarble.by][nmarble.bx] == '#')check[1] = 2;
		
		int rx = nmarble.rx + dx[dir];
		int ry = nmarble.ry + dy[dir];
		int bx = nmarble.bx + dx[dir];
		int by = nmarble.by + dy[dir];

		//print(); //테스트출력
		//다른색 구슬인 경우 + 통로인 경우
		if (rx == nmarble.bx && ry == nmarble.by)	check[0]++;
		else if (map[ry][rx] == '.' && check[0] < 2) {
			nmarble.rx = rx;
			nmarble.ry = ry;
			visualmap[ry][rx] = 'R';
			check[0] = 0;
		}

		if (bx == nmarble.rx && by == nmarble.ry)	check[1]++;
		else if (map[by][bx] == '.' && check[1] < 2) {
			nmarble.bx = bx;
			nmarble.by = by;
			//visualmap[by][bx] = 'B';
			check[1] = 0;
		}
		//벽인 경우 check[0]->red구슬 / check[1]->blue구슬 각 2이면 해당 구슬 동작 멈춤
		if (map[ry][rx] == '#') check[0] = 2;
		if (map[by][bx] == '#') check[1] = 2;

		//blue구슬이 구멍 만나면
		if (by == a.y && bx == a.x) {
			return { 100,100,100,100 };
		}
		//red구슬이 구멍 만나면
		if (ry == a.y && rx == a.x) {
			breaker = 100;
			check[0] = 2;
			nmarble.rx = 11;
			nmarble.ry = 11;
		}
		//종료조건 check가 각 2
		if (check[0] + check[1] == 4)
			break;
	}
	//red구슬이 구멍에 빠진 경우
	if (breaker > 0) {
		mintime = min(mintime, arr.time);
		return { 100,100,100,100 };
	}
	return nmarble;
}

void find_bfs() {
	queue <marble> arr;
	arr.push(o);
	while (!arr.empty()) {
		int rxx = arr.front().rx;
		int ryy = arr.front().ry;
		int bxx = arr.front().bx;
		int byy = arr.front().by;
		int tt = arr.front().time;
		arr.pop();
		for (int i = 0; i < 4; i++) {
			int nx = rxx + dx[i];
			int ny = ryy + dy[i];
			int bnx = bxx + dx[i];
			int bny = byy + dy[i];
			if (map[ny][nx] == '#' && map[bny][bnx] == '#') continue;

			else if (visited[ny][nx][bny][bnx] == 0) {
				marble nextMarble = go(marble{ ryy,rxx,byy,bxx,tt + 1 }, i);
				//visualmap[nextMarble.ry][nextMarble.rx] = 'R';
				//visualmap[nextMarble.by][nextMarble.bx] = 'B';
				visited[ny][nx][bny][bnx] = 1;
				
				//구슬이 구멍에 빠진 경우
				if (nextMarble.bx == 100)
					continue;
				arr.push(nextMarble);
			}
		}
	}
	if (arr.empty() && mintime == 1000)
		mintime = -1;
}

int main(void) {
	input();
	find_bfs();
	if (mintime <= 10)
		cout << mintime << endl;
	else
		cout << -1 << endl;

	return 0;
}

bamgoesn 1년 전 1

10번만에 가능합니다. URDLULDRUR로 이동하면 됩니다.

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

문제

문제

출처

ICPC

(구슬탈출2)예외케이스를 찾긴 했는데, 이 케이스가 왜 이런 답인지 모르겠습니다.

wjd5126 1년 전 1

bamgoesn 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말