글 읽기 - 3190번 뱀문제 완성했는데 어디가 틀린지 모르겠습니다..

dhgks4002 4년 전 0

생각해낸 알고리즘이 맞다고 생각하고 돌렸는데 틀렸습니다..

어느부분이 틀린지 잘 모르겠습니다..

코드가 길지만 도움주시면 감사하겠습니다!

#include <iostream>
#include <queue>
using namespace std;

int map[101][101];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

int n, apple_num, turn_cnt, second;
int pre_direction = 3; 
queue<pair<int, char> > q;  //방향전환 정보 queue 
queue < pair<int, int > > snake;

int turn_right(int cur_d)
{
	q.pop();
	if (cur_d == 0) return 3; 		//북쪽으로 진행중 우회전 -> 동쪽 
	else if (cur_d == 1) return 2;  //남쪽으로 진행중 우회전 -> 서쪽
	else if (cur_d == 2) return 0;  //서쪽으로 진행중 우회전 -> 북쪽
	else if (cur_d == 3) return 1;  //동쪽으로 진행중 우회전 -> 남쪽
}
int turn_left(int cur_d)
{
	q.pop();
	if (cur_d == 0) return 2; 		//북쪽으로 진행중 좌회전 -> 서쪽
	else if (cur_d == 1) return 3;  //남쪽으로 진행중 좌회전 -> 동쪽
	else if (cur_d == 2) return 1;  //서쪽으로 진행중 좌회전 -> 남쪽
	else if (cur_d == 3) return 0;  //동쪽으로 진행중 좌회전 -> 북쪽
}

void solve(int x, int y)
{
	//북 = 0, 남 = 1, 서 = 2, 동 = 3 

	second = 1; //시작은 1초부터 시작 
	int direction = 3; // 첫 방향은 동쪽으로 진행 
	int nx = 0, ny = 0;

	//snake.push(make_pair(x, y)); // 내 꼬리 snake queue에 push 
	while (1)
	{
		nx = x + dx[direction];
		ny = y + dy[direction];

		if (map[nx][ny] == 1 || nx <= 0 || ny <= 0 || nx > n || ny > n)
		{// 다음 움직일곳이 내 몸통이거나 범위를 벗어난다면 현재 second 출력 후 종료 
			cout << second;
			return;
		}
		map[x][y] = 1; //현재몸이 있는곳을 1로 설정 
		snake.push(make_pair(x, y));//꼬리 push

		if (map[nx][ny] == 2) // 다음 움직일곳에 사과가 있다 
		{
			map[nx][ny] = 1; //꼬리 움직이지 않고 사과만 먹음 
			if (pre_direction != direction) //꼬리가 중복되지 않기위해 
			{
				snake.push(make_pair(nx, ny)); //현재위치 push
			}
		}
		else if (map[nx][ny] == 0) //다음움직일곳에 사과가 없다면 
		{
			map[snake.front().first][snake.front().second] = 0; //몸길이 줄여서 꼬리 위치한칸 비우기 
			snake.pop(); //꼬리 pop  
		}

		pre_direction = direction;

		if (!q.empty())	//queue가 비어있어 front값 못받음으로 조건문 생성
		{
			if (second == q.front().first)	//방향 정보시간과 현재 시간이 같다면 
			{
				if (q.front().second == 'D')
				{
					direction = turn_right(direction);
				}
				else if (q.front().second == 'L')
				{
					direction = turn_left(direction);
				}
			}
		}
		x = nx;
		y = ny;
		second++;
	}
}

int main()
{
	cin >> n >> apple_num;
	for (int i = 0; i < apple_num; i++)
	{
		int x = 0;
		int y = 0;
		cin >> x >> y;
		map[x][y] = 2;
	}
	cin >> turn_cnt;

	for (int i = 0; i < turn_cnt; i++)
	{
		int t = 0;
		char d = 0;
		cin >> t >> d;
		q.push(make_pair(t, d));
	}
	solve(1, 1);
	return 0;
}

luniro 4년 전 8

반례드립니다

입력:
5
2
2 5
2 4
6
4 D
5 D
6 D
7 D
8 D
9 D
출력:
10
정답:
14

dhgks4002 4년 전 0

@luniro

반례 정말 감사합니다.

test case를 한 8개정도 해봤는데 전부다 맞고 90 X 90 크기정도의 테스트에서 막혀 디버깅하기가 힘들었습니다.

저 반례로 디버깅해보니 얼마 안걸려 해결방법을 찾았던것 같습니다.

방향전환 정보를 먼저 받아왔어야했고 또한 snake queue에 정보를 넣는 방식도 잘못됐다는것을 알게되었습니다.

도움 감사합니다

kimkyu1515 4년 전 0

대박...저도 같은데서 틀렸었네요...반례 감사합니다

wnduq125 2년 전 0

luniro

반례 감사드립니다.

제 경우에는 사과를 먹고 나서, 먹었다는 처리를 해주지 않아 오류가 발생했습니다.

오류때문에 들어오신 분들 참고하시기 바랍니다.

hky5820 2년 전 0

반례 감사드립니다.

저도 wnduq125님과 동일하게 사과를 먹고나서 먹었다는 처리를 안해줘서 오류가 발생했었습니다.

정말 좋은 반례 감사드립니다.

tndyd0706 2년 전 0

먹은거 처리하니깐 됐어요!

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

문제

문제

출처

ICPC

3190번 뱀문제 완성했는데 어디가 틀린지 모르겠습니다..

dhgks4002 4년 전 0

luniro 4년 전 8

dhgks4002 4년 전 0

kimkyu1515 4년 전 0

wnduq125 2년 전 0

hky5820 2년 전 0

tndyd0706 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말