글 읽기 - 로봇 문제 원인을 잘 모르겠는데 설명좀 해주실수있나요.

madcatlove 7년 전 1

원래 코드는 82번 라인을 주석을 풀고 (break 대신 continue를 사용하였습니다.)

마지막 원하는 결과인

visited[ey][ex][ed] 에 담긴값이 최적의 값이라 생각하여 그 값을 출력하려했는데

도무지 예제 케이스조차 답이 안나와서

쭉 살펴보다가 continue 부분 대신에 break 해도 무방할거 같아 수정했는데

답이 뚝하고 나왔습니다.

(물론 원하는 visited[ey][ex][ed]에 답이 담긴건 아닌데요....)

continue를 사용해도 .. 그리고 어짜피 visited[ey][ex][ed]에 답이 최적으로 담기는 경우가 발생하지 않나요??

#include <cstdio>
#include <queue>
#define INF 987654321
using namespace std;

int row, col;
int matrix[111][111];
int visited[111][111][5];
const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };

int sy, sx, sd;
int ey, ex, ed;

typedef struct {
	int y;
	int x;
	int dir;
} DT;

int outofrange(int y, int x) {
	return (y < 0 || y >= row || x < 0 || x >= col || matrix[y][x] != 0);
}

int rotate(int a, int b) {
	a++; b++;

	if (a == b) return 0;
	if (a == 1 && b == 2) return 2;
	if (a == 2 && b == 1) return 2;
	if (a == 3 && b == 4) return 2;
	if (a == 4 && b == 3) return 2;
	return 1;

}

int main() {

	scanf("%d %d", &row, &col);
	for (int y = 0; y < row; y++) {
		for (int x = 0; x < col; x++) {
			scanf("%d", &matrix[y][x]);

			for (int k = 0; k < 5; k++) visited[y][x][k] = INF;
		}
	}
	
	scanf("%d %d %d", &sy, &sx, &sd);
	scanf("%d %d %d", &ey, &ex, &ed);

	sy--; sx--; sd--;  ey--; ex--; ed--;

	queue<DT> q;
	q.push(DT{ sy, sx, sd });
	visited[sy][sx][sd] = 0;

	while (!q.empty()) {
		int cx = q.front().x;
		int cy = q.front().y;
		int cdir = q.front().dir;
		q.pop();

		//printf("cy : %d cx  :%d , cdir :%d\n", cy, cx, cdir);
		if (cy == ey && cx == ex) {
			printf("%d\n",visited[cy][cx][cdir] + rotate(cdir,ed) );
			break;
		}
		
		// 방향 전환
		for (int dir = 0; dir < 4; dir++) {
			int rotatePrice = rotate(cdir, dir);
			int nx = cx;
			int ny = cy;

			// 그때마다 점프뜀
			for (int k = 1; k <= 3; k++) {
				nx = nx + dx[dir];
				ny = ny + dy[dir];


				if (outofrange(ny, nx)) break;
				// if (outofrange(ny, nx)) continue; (이부분을 하면 왜 안될까 )

				if (visited[cy][cx][cdir] + 1 + rotatePrice < visited[ny][nx][dir]) {
					q.push(DT{ ny, nx, dir });
					visited[ny][nx][dir] = visited[cy][cx][cdir] + 1 + rotatePrice;
				}
			}


		}
		
	}

	return 0;
}

madcatlove 7년 전 1

자답입니다.

K=1 만큼 이동할때 벽을 만났으면 그 이후 K=2, 3 은 당연히 안됩니다.

continue를 했었다면...

2,3이 벽을 체크를 안했기 때문에 된다고 판단하고 오답이 나올 수 있네요...

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

문제

문제

출처

ICPC

로봇 문제 원인을 잘 모르겠는데 설명좀 해주실수있나요.

madcatlove 7년 전 1

madcatlove 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말