글 읽기 - 구슬탈출2 틀렸습니다 제발 도와주세요 ㅠㅠ

flytmdgh 4년 전 0

질문 게시판의 약 100개가 넘는 테스트케이스와 예제 모두 통과했는데 44%에서 틀렸습니다가 떠요

틀렸습니다=제 코드 알고리즘 중 틀린 곳이 있다라고 생각해서 다시 차근히 읽어 봤는데 못찾겠더라구요 ㅠㅠ

제 코드는 C로 BFS로 구현한거예요. 주석은 달아놨지만 다른 함수는 특별한거 없고 enqueue함수랑 canmove함수가 핵심인데

canmove에서 방향이 제시되고 갈 수 있다면 enqueue함수하는 방식입니다.

코드는 좀 길지만 틀렸다면 저 두 함수에서 틀렸을 가능성이 높습니다 ㅠㅠ

반례나 코드 오류 발견해주시면 댓글달아주시면 감사하겠습니다!!

#include <stdio.h>
	typedef struct point {
		int x;
		int y;
	}point;
	typedef struct coco {//queue에 들어가는 구조체

		int time;  //몇 번째 기울인지 나타나는 것
		point red, blue;
		int dir; //어디로 기울이는지 방향
	}coco;

	coco queue[5000000];
	int front, rear;
	int board[11][11]; //입력받은 문자를 숫자로 바꿔준 배열

	int empty() {  //큐를 끝내기 위해 넣은 함수
		if (front == rear) {
			return 0;
		}
		else {
			return 1;
		}
	}
	point hole, red, blue;
	int n, m;
	char hrr[11][11];//입력받는 곳으로 큰의미 x
	void enqueue(int dir, int num, point red, point blue) {
		queue[rear].dir = dir;
		switch (dir)
		{
		case 0://왼쪽으로 기울 일때

			if (red.x == blue.x) {//같은 x좌표라면 겹치는 것 생각
				if (red.y > blue.y) {//파란게 더 왼쪽에 있다면 파란거 먼저 이동시킴
					for (int i = 1; i < blue.y + 1; i++) {
						if (board[blue.x][blue.y - i] == 1) {
							queue[rear].blue.y = blue.y - i + 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
							queue[rear].blue.x = blue.x;
							break;
						}

					}//파랑먼저 보내고
					for (int i = 1; i < red.y + 1; i++) {
						if ((board[red.x][red.y - i] == 1) || ((red.x == queue[rear].blue.x) && (red.y - i == queue[rear].blue.y))) {//가다가 벽이나 파랑만나면
							queue[rear].red.y = red.y - i + 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
							queue[rear].red.x = red.x;
							break;
						}
						else if (board[red.x][red.y - i] == 2) {
							queue[rear].red.y = hole.y;
							queue[rear].red.x = hole.x;
							break;
						}
					}
				}
				else {//빨간게 더 왼쪽이라 빨간거를 먼저 이동시킴
					for (int i = 1; i < red.y + 1; i++) {//벽 만났을 때
						if (board[red.x][red.y - i] == 1) {
							queue[rear].red.y = red.y - i + 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
							queue[rear].red.x = red.x;
							break;
						}
						else if (board[red.x][red.y - i] == 2) {//구멍만났을 때
							queue[rear].red.y = hole.y;
							queue[rear].red.x = hole.x;
							break;
						}
					}
					for (int i = 1; i < blue.y + 1; i++) {
						if ((board[blue.x][blue.y - i] == 1) || ((queue[rear].red.x == blue.x) && (blue.y - i == queue[rear].red.y))) {//가다가 벽이나 파랑만나면
							queue[rear].blue.y = blue.y - i + 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
							queue[rear].blue.x = blue.x;
							break;
						}
					}

				}
			}
			else {//안 겹치면			
				for (int i = 1; i < red.y + 1; i++) {
					if ((board[red.x][red.y - i] == 1)) {
						queue[rear].red.y = red.y - i + 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
						queue[rear].red.x = red.x;
						break;
					}
					else if (board[red.x][red.y - i] == 2) {
						queue[rear].red.y = hole.y;
						queue[rear].red.x = hole.x;
						break;
					}

				}
				for (int i = 1; i < blue.y + 1; i++) {
					if (board[blue.x][blue.y - i] == 1) {
						queue[rear].blue.y = blue.y - i + 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
						queue[rear].blue.x = blue.x;
						break;
					}
				}
			}
			break;
		case 1://우
			if (red.x == blue.x) {//같은 x좌표라면 겹치는 것 생각
				if (red.y < blue.y) {
					for (int i = 1; i < m - blue.y; i++) {
						if (board[blue.x][blue.y + i] == 1) {
							queue[rear].blue.y = blue.y + i - 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
							queue[rear].blue.x = blue.x;
							break;
						}


					}//파랑먼저 보내고
					for (int i = 1; i < m - red.y; i++) {
						if ((board[red.x][red.y + i] == 1) || ((red.x == queue[rear].blue.x) && (red.y + i == queue[rear].blue.y))) {//가다가 벽이나 파랑만나면
							queue[rear].red.y = red.y + i - 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
							queue[rear].red.x = red.x;
							break;
						}
						else if (board[red.x][red.y + i] == 2) {
							queue[rear].red.y = hole.y;
							queue[rear].red.x = hole.x;
							break;
						}
					}
				}
				else {
					for (int i = 1; i < m - red.y; i++) {
						if (board[red.x][red.y + i] == 1) {
							queue[rear].red.y = red.y + i - 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
							queue[rear].red.x = red.x;
							break;
						}
						else if (board[red.x][red.y - i] == 2) {
							queue[rear].red.y = hole.y;
							queue[rear].red.x = hole.x;
							break;
						}
					}
					for (int i = 1; i < m - blue.y; i++) {
						if ((board[blue.x][blue.y + i] == 1) || ((queue[rear].red.x == blue.x) && (blue.y + i == queue[rear].red.y))) {//가다가 벽이나 파랑만나면
							queue[rear].blue.y = blue.y + i - 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
							queue[rear].blue.x = blue.x;
							break;
						}
					}

				}
			}
			else {//안 겹치면			
				for (int i = 1; i < m - red.y; i++) {
					if (board[red.x][red.y + i] == 1) {
						queue[rear].red.y = red.y + i - 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
						queue[rear].red.x = red.x;
						break;
					}
					else if (board[red.x][red.y + i] == 2) {
						queue[rear].red.y = hole.y;
						queue[rear].red.x = hole.x;
						break;
					}

				}
				for (int i = 1; i < m - blue.y; i++) {
					if (board[blue.x][blue.y + i] == 1) {
						queue[rear].blue.y = blue.y + i - 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
						queue[rear].blue.x = blue.x;
						break;
					}
				}
			}
			break;

		case 2://위
			if (red.y == blue.y) {//같은 x좌표라면 겹치는 것 생각
				if (red.x > blue.x) {
					for (int i = 1; i < blue.x + 1; i++) {
						if (board[blue.x - i][blue.y] == 1) {
							queue[rear].blue.x = blue.x - i + 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
							queue[rear].blue.y = blue.y;
							break;
						}

					}//파랑먼저 보내고
					for (int i = 1; i < red.x + 1; i++) {
						if ((board[red.x - i][red.y] == 1) || ((red.x - i == queue[rear].blue.x) && (red.y == queue[rear].blue.y))) {//가다가 벽이나 파랑만나면
							queue[rear].red.x = red.x - i + 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
							queue[rear].red.y = red.y;
							break;
						}
						else if (board[red.x - i][red.y] == 2) {
							queue[rear].red.y = hole.y;
							queue[rear].red.x = hole.x;
							break;
						}
					}
				}
				else {
					for (int i = 1; i < red.x + 1; i++) {
						if (board[red.x - i][red.y] == 1) {
							queue[rear].red.x = red.x - i + 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
							queue[rear].red.y = red.y;
							break;
						}
						else if (board[red.x - i][red.y] == 2) {
							queue[rear].red.y = hole.y;
							queue[rear].red.x = hole.x;
							break;
						}
					}
					for (int i = 1; i < blue.x + 1; i++) {
						if ((board[blue.x - i][blue.y] == 1) || ((queue[rear].red.x == blue.x - i) && (blue.y == queue[rear].red.y))) {//가다가 벽이나 파랑만나면
							queue[rear].blue.x = blue.x - i + 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
							queue[rear].blue.y = blue.y;
							break;
						}
					}

				}
			}
			else {//안 겹치면			
				for (int i = 1; i < red.x + 1; i++) {
					if (board[red.x - i][red.y] == 1) {
						queue[rear].red.x = red.x - i + 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
						queue[rear].red.y = red.y;
						break;
					}
					else if (board[red.x - i][red.y] == 2) {
						queue[rear].red.y = hole.y;
						queue[rear].red.x = hole.x;
						break;
					}

				}
				for (int i = 1; i < blue.x + 1; i++) {
					if (board[blue.x - i][blue.y] == 1) {
						queue[rear].blue.x = blue.x - i + 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
						queue[rear].blue.y = blue.y;
						break;
					}
				}
			}
			break;

		case 3:
			if (red.y == blue.y) {//같은 x좌표라면 겹치는 것 생각
				if (red.x < blue.x) {
					for (int i = 1; i < n - blue.x; i++) {
						if (board[blue.x + i][blue.y] == 1) {
							queue[rear].blue.x = blue.x + i - 1;
							queue[rear].blue.y = blue.y;
							break;
						}

					}//파랑먼저 보내고
					for (int i = 1; i < n - red.x; i++) {
						if ((board[red.x + i][red.y] == 1) || ((red.x + i == queue[rear].blue.x) && (red.y == queue[rear].blue.y))) {//가다가 벽이나 파랑만나면
							queue[rear].red.x = red.x + i - 1;
							queue[rear].red.y = red.y;
							break;
						}
						else if (board[red.x + i][red.y] == 2) {
							queue[rear].red.y = hole.y;
							queue[rear].red.x = hole.x;
							break;
						}
					}
				}
				else {
					for (int i = 1; i < n - red.x; i++) {
						if (board[red.x + i][red.y] == 1) {
							queue[rear].red.x = red.x + i - 1;
							queue[rear].red.y = red.y;
							break;
						}
						else if (board[red.x + i][red.y] == 2) {
							queue[rear].red.y = hole.y;
							queue[rear].red.x = hole.x;
							break;
						}
					}
					for (int i = 1; i < n - blue.x; i++) {
						if ((board[blue.x + i][blue.y] == 1) || ((queue[rear].red.x == blue.x + i) && (blue.y == queue[rear].red.y))) {//가다가 벽이나 파랑만나면
							queue[rear].blue.x = blue.x + i - 1;
							queue[rear].blue.y = blue.y;
							break;
						}
					}

				}
			}
			else {//안 겹치면			
				for (int i = 1; i < n - red.x; i++) {
					if (board[red.x + i][red.y] == 1) {
						queue[rear].red.x = red.x + i - 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
						queue[rear].red.y = red.y;
						break;
					}
					else if (board[red.x + i][red.y] == 2) {
						queue[rear].red.y = hole.y;
						queue[rear].red.x = hole.x;
						break;
					}

				}
				for (int i = 1; i < n - blue.x; i++) {
					if (board[blue.x + i][blue.y] == 1) {
						queue[rear].blue.x = blue.x + i - 1;//왼쪽으로가다가 1을 만나면 그거에 바로 오른쪽꺼
						queue[rear].blue.y = blue.y;
						break;
					}
				}
			}
			break;
		}

		queue[rear].time = num;

		rear++;
		return;
	}
	coco dequeue() {

		return queue[front++];
	}
	int canmove(int dir, point red, point blue) {
		int temp = 0;
		switch (dir)
		{
		case 0:			
					
			for (int i = 1; i < blue.y + 1; i++) {
				if (board[blue.x][blue.y - i] == 1) {//왼쪽에 홀보다 벽먼저 만나면 가능!
					return 1;
				}
				else if ((blue.x == hole.x) && (blue.y - i == hole.y)) {
					return 0;
				}
				//중간에 빨간색이 있더라도 그냥 지나친다.
			}			
			break;

		case 1:
			for (int i = 1; i < m - blue.y; i++) {
				if (board[blue.x][blue.y + i] == 1) {
					return 1;
				}
				else if ((blue.x == hole.x) && (blue.y + i == hole.y)) 
					return 0;
				}
				//중간에 빨간색이 있더라도 그냥 지나친다.
			
			break;

		case 2://위쪽			
			for (int i = 1; i < blue.x + 1; i++) {
				if (board[blue.x - i][blue.y] == 1) {
					return 1;
				}
				else if ((blue.x - i == hole.x) && (blue.y == hole.y)) {
					return 0;
				}
				//중간에 빨간색이 있더라도 그냥 지나친다.
			}			
			break;


		case 3://아래										
			for (int i = 1; i < n - blue.x; i++) {
				if (board[blue.x + i][blue.y] == 1) {
					return 1;
				}
				else if ((blue.x + i == hole.x) && (blue.y == hole.y)) {
					return 0;
				}
				//중간에 빨간색이 있더라도 그냥 지나친다.
			}
			break;
		}
		return 1;
	}
	int main(void) {
	//	char tototo;
		scanf("%d%d\n", &n, &m);
		//scanf("%c",&tototo,sizeof(tototo));
		for (int i = 0; i < n; i++) {	
				scanf_s("%s",hrr[i], sizeof(hrr[i]));					
		}	
	
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (hrr[i][j] == '#') {
					board[i][j] = 1;
				}
				else if (hrr[i][j] == '.') {
					board[i][j] = 0;
				}
				else if (hrr[i][j] == 'O') {
					hole.x = i;
					hole.y = j;
					board[i][j] = 2;
				}
				else if (hrr[i][j] == 'R') {
					red.x = i;
					red.y = j;
					board[i][j] = 3;
				}
				else if (hrr[i][j] == 'B') {
					blue.x = i;
					blue.y = j;
				board[i][j] = 4;
				}
			}


		}
			
		for (int i = 0; i < 4; i++) {
			if (canmove(i, red, blue) == 1) {//0 1 2 3 은 각각 왼 오른 위 아래			
				enqueue(i, 1, red, blue);
			}
		}
		coco q;
		while (empty() == 1) {
			q = dequeue();
		//	printf("dequeue한얘들 blue[%d%d],red[%d][%d] 방향%d 몇번째 얘들 %d\n", q.blue.x, q.blue.y, q.red.x, q.red.y, q.dir, q.time);
			if (q.time > 10) {
				printf("-1");
				return 0;
			}
			if ((q.red.x == hole.x) && (q.red.y == hole.y)) {
				printf("%d", q.time);
				return 0;
			}
			for (int i = 0; i < 4; i++) {//이전 방향에서 왼쪽으로 이동했다면 다음번에 오른쪽으로 이동할 필요는 없으므로                
				if (q.dir == 0) {//넣어준 코드
					if (i != 1) {
						if (canmove(i, q.red, q.blue) == 1) {//0 1 2 3 은 각각 왼 오른 위 아래
							enqueue(i, q.time + 1, q.red, q.blue);
						}
					}
				}
				if (q.dir == 1) {
					if (i != 0) {
						if (canmove(i, q.red, q.blue) == 1) {//0 1 2 3 은 각각 왼 오른 위 아래
							enqueue(i, q.time + 1, q.red, q.blue);
						}
					}
				}
				if (q.dir == 2) {
					if (i != 3) {
						if (canmove(i, q.red, q.blue) == 1) {//0 1 2 3 은 각각 왼 오른 위 아래
							enqueue(i, q.time + 1, q.red, q.blue);
						}
					}
				}
				if (q.dir == 3) {
					if (i != 2) {
						if (canmove(i, q.red, q.blue) == 1) {//0 1 2 3 은 각각 왼 오른 위 아래
							enqueue(i, q.time + 1, q.red, q.blue);
						}
					}
				}
			}
		}
		printf("-1");
	
	}

surung9898 4년 전 1

https://boohyunsik.github.io/exit-marble-test-case/

여기도 확인하셨나요?

flytmdgh 4년 전 0

답변 감사합니다!!
네 하느라 팔빠지는 줄알았지만 모조리 다해봤어요..공교롭게도 다 일치하네요..

어떤 특이케이스에서 걸렸을까요..ㅠㅠ

tony9402 3년 전 2

반례 드립니다.

6 9
#########
####....#
#..#.##.#
###..#..#
#B##.RO.#
#########

answer : 1

5 10
##########
#O.......#
##B.R...##
###.##...#
##########

answer : 4

5 10
##########
####.##O.#
#.BR.....#
#...##.###
##########

answer : -1

7 8
########
#.#.#.##
########
#...#..#
#.OBR..#
##.##..#
########

answer : 2

flytmdgh 3년 전 0

아 답변 감사합니다 오른쪽으로 기울일 때 red가 왼쪽으로 가게 설정이 되어있었네요. 부호 하나로 진짜 몇시간을 날린지 ㅋㅋㅋㅋ

반레 정말 감사합니다!!!

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

문제

문제

출처

ICPC

구슬탈출2 틀렸습니다 제발 도와주세요 ㅠㅠ

flytmdgh 4년 전 0

surung9898 4년 전 1

flytmdgh 4년 전 0

tony9402 3년 전 2

flytmdgh 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말