글 읽기 - 째로탈출1은 풀리는데 2가 92%에서 틀립니다.

selgun05 4년 전 0

ttps://www.acmicpc.net/proble...

똑같은 문젠데

10번 이하로 뺄 수 있는지 없는지만 알아내는 문제인데 여기서는 정답나옵니다.

근데 이건 92%에서 틀렸습니다. 가 나오네요.

현재 코드는 틀린거로 나오고

이유는 모르겠는데 map[10->12][10->12]로 선언하면 런타임오류 뜹니다. ... 11, 11까진 괜찮구요 메모리가 후달린가..?

째로1이 된걸 보면 10번 초과, 아닌건 구별가능한데 10번 미만으로 탐색이 될 때 횟수계산을 못하는 경우가 있다고 판단하고 있습니다.

기울이는 경우의 수는 처음엔 4가지, 그다음엔 방금 기울인 방향 기준 좌 우 두가지가 있다고 생각했구요.

구슬 움직이면서 경우의 수는

진행방향에서 두 구슬이 다른 줄에 있을 때 -> 들어간 거는 단순하게 따로 체크

진행방향에서 두 구슬이 한줄로 있을 때 -> 빨강공 먼저 or 파란공 먼저움직이는지 체크

이 때 둘다 들어가는지 하나만 들어가는지도 체크 했습니다.

각각 이프문으로 구별해낸 건 아닌데, state가 기본이 0으로 초기화한것, 공을 이동하는 순서를 두어서 파란공이 빠지면 -1이고 빨간공만 빠지면 1이 되게끔 구현했습니다.

(즉, <-, ->으로 움직일 때 R~~O~~B, R~~B~~O, O~~R~~B 에서 성공인지 실패인지 구별이 되게끔 했음 (제 생각엔))

도와주시면 정말 감사하겠습니다.

코드 설명 추가로 드리면

맵을 입력 받음, 맵에서 R B는 빈 통로문자인 . 으로 바꿈, 대신에 각 구슬의 위치를 구조체 xy r, b에서 기억함
dfs를 할건데 처음으로 실행하기전 조건은 두 구슬중 하나라도 움직일 수 있으면 실행함, 조건에 맞는 동서남북 방향에 대해서 실행
dfs내부에서 실행 조건(또 기울여야 하는 경우)은 길 탐색이 안끝난 경우(구슬이 안빠지거나, 움직일수 있거나, 기울인 횟수가 10번 미만인 경우)에 이전에 기울인 방향기준 좌, 우 방향으로 대해서 dfs를 재귀적으로 실행
dfs내에선 3가지 state를 가짐, 성공, 탐색중, 실패.. ->성공, 실패인 경우 3. 조건에서 길 탐색이 끝난경우로 처리함 + 성공하면 성공까지의 기울임 횟수(suc_cnt)를 업데이트함

아 그리고 방향 값은 0 1 2 3이 서북동남 순입니다..

우, 좌는 +1더하고 +3더한거에서 4나눠서 계산했어요...

————————————————————-

혹시나해서 map을 12 by 12 로 세팅하고 벽으로 한바퀴 둘렀더니

해결됐습니다 이유는 모르겠네요

혹시 92%에서 틀리시는 분들 참고하시고 원인 아시는 분들은 알려주시면 감사하겠습니다

-----------------------------------------------

설마했는데 테스트케이스 문제였네요 해결됐습니다 -.,-..

#include <iostream>
#include <algorithm>
using namespace std;
#define R(x) ((x+1)%4)	//right direction
#define L(x) ((x+3)%4)	//left d..
// W, N, E, S
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };

int n, m;

typedef struct xy {
	int x;
	int y;
}xy;

int suc_cnt = 777;
char map[10][10];

// 진행방향 바로 앞칸으로 가도되는지 판단 p는 확인할 구슬, q는 다른 구슬
int valid_xy(xy p, xy q, int d) {
	int x = p.x + dx[d];
	int y = p.y + dy[d];
	// No!, Wall or other ball
	if (map[y][x] == '#' || (q.x == x && q.y == y))
		return -1;
	else if (map[y][x] == 'O')	// Holl
		return 1;
	else						// OK
		return 0;
}

// valid_xy 함수 이용하여 진행방향으로 보냄, p는 움직일 구슬, q는 다른 구슬
int go_xy(xy &p, xy q, int d) {

	while (1) {
		int ret = valid_xy(p, q, d);
		if (ret == 0) {		//한칸 전진
			p.x += dx[d];
			p.y += dy[d];
		}
		else if (ret == 1) { // exit, 탈출임
			p.x = 0;
			p.y = 0;
			return 1;
		}
		else if (ret == -1) { // Wall or ball
			return 0;
		}
	}
}

void dfs(xy r, xy b, int cnt, int d)
{
	int state = 0; // success : 1, 탐색중 : 0, fail : -1

	// 다른 선상
	if ((d % 2 == 0 && r.y != b.y) || (d % 2 == 1 && r.x != b.x)) {
		if (go_xy(r, b, d) == 1)	// 빨간 구슬 골인
			state = 1;
		
		if (go_xy(b, r, d) == 1)	// 파랑 구슬 골인
			state = -1;
	}

	// 동일 선상에서 빨간공이 먼저 가는 경우
	else if ((d == 0 && r.x < b.x) || (d == 2 && r.x > b.x) || (d == 1 && r.y < b.y) || (d == 3 && r.y > b.y)) {
		if (go_xy(r, b, d) == 1)	// 빨간 구슬 골인
			state = 1;

		if (go_xy(b, r, d) == 1)	// 파랑 구슬 골인
			state = -1;				// 빨강들가도 파랑 들어가면 실패
	}

	// 동일 선상에서 파란공이 먼저 가는 경우  
	else {
		if (go_xy(b, r, d) == 1)	// 파랑 구슬 골인
			state = -1;
		
		if (go_xy(r, b, d) == 1) {	// 빨간 구슬 골인, 
			if (state == 0)			// 빨강들가도 파랑 안들어가야 성공
				state = 1;
		}
	}

	if (state == 1) 
		suc_cnt = min(suc_cnt, cnt);		//success->update 기울임 횟수 최소값으로
	
	else if (state == 0 && cnt < 10) {		//more search
		if (valid_xy(r, b, R(d)) >= 0 || valid_xy(b, r, R(d)) >= 0)
			dfs(r, b, cnt + 1, R(d));
		if (valid_xy(r, b, L(d)) >= 0 || valid_xy(b, r, L(d)) >= 0)
			dfs(r, b, cnt + 1, L(d));
	}//else -> state = -1 or cnt >=10 함수 종료
}

int main() {

	xy r, b;	// 구슬 좌표
	cin >> n >> m;
	cin.ignore();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int c = cin.get();
			if (c == 'R') {
				r.x = j;
				r.y = i;
				c = '.';
			}
			else if (c == 'B') {
				b.x = j;
				b.y = i;
				c = '.';
			}
			map[i][j] = c;
		}
		cin.ignore();
	}

	for (int i = 0; i < 4; i++) {
		if (valid_xy(r, b, i) >= 0 || valid_xy(b, r, i) >= 0)
			dfs(r, b, 1, i);
	}

	if (suc_cnt == 777)	// 탐색 전부 실패
		cout << -1;	
	else
		cout << suc_cnt;
}

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

문제

문제

출처

ICPC

째로탈출1은 풀리는데 2가 92%에서 틀립니다.

selgun05 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말