글 읽기 - 로직 잘 짜여진것 같은데 어디가 틀린건지 알려주실 교수님 계신가요 ㅠ

goodjaeheui 4년 전 0

먼저 로직은

메인에서 1,2,3,4인 동서남북을 회전을 편하게 시키기 위해 남동서북 0,1,2,3으로 바꿨습니다.

그런다음 bfs함수로 들어가서

구조체( x,y,방향, 직진 몇번했는지 알려주는 변수(goCount),현재 시간)를 가진 큐를 생성합니다.

for문 안에 3개의 반복을 거치는데

먼저 직진 {

goCount값이 0이면 시간 1카운트

goCount 카운트시키고

만약 goCount값이 3이면 (즉 3번 직진한 상태면 0으로 다시 초기화)

}

그다음 왼쪽회전{

방향값을 +1 해준다.

time값+1 과 goCount=0으로 초기화

}

그다음 오른쪽회전 {

방향값을 -1 해줘야하지만 음수를 고려해서 (d+3)%4 로 했습니다

time값+1 과 goCount=0으로 초기화

}

이렇게 로직이 잘 구현돼 있다고 생각하는데 어떤부분에서 틀린건지 잘 모르겠습니다. 질문에 있던 테케랑 제가 만든 반례도 다 맞구요..

// #b1726 로봇	time:
#include <iostream>
#include <queue>
using namespace std;

int arr[101][101];
int visit[101][101][4];
int dir[4][2] = { {1,0}, { 0,1 }, { -1,0 }, { 0,-1 } };//동서남북
int n, m;

typedef struct xyd {
	int x, y, d;
}xyd;
xyd st;
xyd ed;

typedef struct info {
	int x, y, d;
	int goCount;
	int nowtime;
}info;

void bfs() {
	queue<info> q;
	q.push({ st.x, st.y, st.d, 0, 0 });
	visit[st.x][st.y][st.d] = true;

	while (!q.empty()) {
		int fx = q.front().x;
		int fy = q.front().y;
		int fd = q.front().d;
		int goCount = q.front().goCount;
		int nowtime = q.front().nowtime;
		q.pop();

		//cout << "fx " << fx << " fy " << fy << " fd " << fd << " goCount " << goCount << " nowtime " << nowtime << endl;
		if (fx == ed.x&&fy == ed.y&&fd == ed.d) {
			cout << nowtime << '\n';
			return;
		}

		for (int i = 0; i < 3; i++) {
			int nx = fx, ny = fy, nd = fd, ngoCount = goCount, ntime = nowtime;
			// 그대로 진행  goCount가 1,2,3이면 nowtime 증가 ㄴㄴ
			if (i == 0) {
				nx = fx + dir[fd][0]; ny = fy + dir[fd][1];
				if (ngoCount == 0)ntime = nowtime + 1;
				ngoCount++;
				if (ngoCount == 3)ngoCount = 0;
			}

			// 왼쪽회전 time 증가
			else if (i == 1) {
				nd = (fd + 1) % 4;
				ntime = nowtime + 1;
				ngoCount = 0;
			}

			// 오른쪽 회전 time 증가
			else if (i == 2) {
				nd = (fd + 3) % 4;
				ntime = nowtime + 1;
				ngoCount = 0;
			}

			if (nx <= 0 || nx > n || ny <= 0 || ny > m)continue;
			if (visit[nx][ny][nd])continue;
			if (arr[nx][ny] == 1)continue;
			visit[nx][ny][nd] = true;
			q.push({ nx,ny,nd,ngoCount,ntime });
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];

		}
	}
	int x, y, d;
	cin >> x >> y >> d;
	//회전시키기 편하게 변환
	if (d == 2)d = 3;
	else if (d == 3)d = 0;
	else if (d == 4)d = 2;
	st = { x,y,d };
	cin >> x >> y >> d;
	if (d == 2)d = 3;
	else if (d == 3)d = 0;
	else if (d == 4)d = 2;
	ed = { x,y,d };
	bfs();
}

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

문제

문제

출처

ICPC

로직 잘 짜여진것 같은데 어디가 틀린건지 알려주실 교수님 계신가요 ㅠ

goodjaeheui 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말