글 읽기 - 1726 틀렸습니다....

axa1239 4년 전 0

코드의 설명은 다음과 같습니다.

크게 BFS 를 사용 하였습니다 - > 저같은 경우

// 북쪽을 0
// 동쪽을 1
// 남쪽을 2
// 서쪽을 3

을 사용하여 입력받는 즉시 다음과 같이 수정을 해주었습니다. - > changeDir 함수를 통해서

전체적인 로직은 다음과 같습니다.

1. 큐에 x, y, d(방향) 을 넣어 주고 - > BFS 수행

2. 총 3가지의 명령이 가능

1). 현재의 위치와 방향대로 직진을 한다

벽에 부딪히거나 좌표를 벗어나는 경우를 제외하고 그전 까지는 방문하지 않은 값이라면( BFS 이므로 최소가 보장 되니깐) 큐에 이동한 좌표 와 방 향 은 큐에 다시 넣어 줍니다.

2). 현재의 좌표 방향에서 왼쪽으로 회전만 해준다 이 경우에도 방문 한적이 없다면 dist[x][y][nd] == -1 인경우 큐에 값을 넣어줌

3). 현재의 좌표 방향에서 오른쪽으로 회전만 해준다 이 경우에도 방문 한적이 없다면 dist[x][y][nd] == -1 인경우 큐에 값을 넣어줌

3. 큐에서 값을 꺼냈을 때. 목적지와 같다면 dist[x][y][d] 값을 출력하주고 종료합니다..

여러가지 테스트 케이스도 맞고 예제 입력 또한 결과가 제대로 나오지만 어디가 잘못된것인지 잘 모르겠습니다... 제가 놓치고 있는 부분이나 코드가 잘못된 곳이 있나요?..

도움 부탁드립니다 ㅠㅠㅠㅠㅠ

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <string>
#include <tuple>
using namespace std;
const int MAX = 101;
int map[MAX][MAX];
int dist[MAX][MAX][4];
int n, m;
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };

bool isInRange(int x, int y) {
	if (1 <= x && x <= n && 1 <= y && y <= m) return true;
	return false;
}

//  북쪽을 0 
//  동쪽을 1
//  남쪽을 2
//  서쪽을 3
int changeDir(int d) {
	if (d == 1) return d;
	else if (d == 2) return 3;
	else if (d == 3) return 2;
	else return 0;
}

int main() {

	int sx, sy, sd, ex, ey, ed;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> map[i][j];
		}
	}
	cin >> sx >> sy >> sd >> ex >> ey >> ed;
	sd = changeDir(sd);
	ed = changeDir(ed);
	memset(dist, -1, sizeof(dist));
	dist[sx][sy][sd] = 0;
	queue<tuple<int, int, int>> q;
	q.push({ sx, sy, sd });
	while (!q.empty()) {
		int x, y, d;
		tie(x, y, d) = q.front();
		q.pop();
		if (x == ex && y == ey && d == ed) {
			cout << dist[ex][ey][ed] << '\n';
			return 0;
		}
		// 총 3가지 명령이 가능 하다.

		// commands 가 0일 경우 - > 현재 방향에서 직진을 한다
		//			   1일 경우 왼쪽 방향으로 전환을 한다.
		//			   2일 경우 오른쪽 방향으로 전환을 한다.

		for (int commands = 0; commands < 3; commands++) {
			if (commands == 0) {
				for (int k = 1; ; k++) {
					int nx = x + (dx[d] * k);
					int ny = y + (dy[d] * k);
					if (map[nx][ny] == 1) break;
					if (!isInRange(nx, ny)) break;
					if (dist[nx][ny][d] == -1) {
						dist[nx][ny][d] = dist[x][y][d] + 1;
						q.push({ nx, ny, d });
					}
				}
			}
			else if (commands == 1) {
				// 왼쪽으로 방향을 전환
				int nd = d - 1;
				if (nd == -1) nd = 3;
				if (dist[x][y][nd] == -1 ) {
					dist[x][y][nd] = dist[x][y][d] + 1;
					q.push({ x, y, nd });
				}
			}
			else {
				// 오른쪽으로 방향을 전환
				int nd = d + 1;
				if (nd == 4) nd = 0;
				if (dist[x][y][nd] == -1) {
					dist[x][y][nd] = dist[x][y][d] + 1;
					q.push({ x, y, nd });
				}

			}
		}
	}
	return 0;
}

culture1123 4년 전 1

정답 지점에 도착하면 바로 리턴하는거,

방향 이동할때 180도면 +2 해야하는거 참조해보세요

axa1239 4년 전 0

답변 감사드립니다.. 아직도 해결 못하였네요

제가 문제를 잘 못 이해하고 있는 건가요..?

BFS로 구현 하기 때문에 최소 명령 횟수가 보장 되어 정답 지점에가면 바로 return 하고 끝내도 되는것 아닌가요..?

제 코드 같은 경우 밑에와 같이 수정 해주었고

// 북쪽을 0
// 동쪽을 1
// 남쪽을 2
// 서쪽을 3

왼쪽 또는 오른 쪽으로 90도 회전 가능 하기 때문에 +1 or -1 로서 위의 코드와 같이 구현해 주었습니다..

말씀 하시는게 정확히 어떤 부분인지 잘 모르겠습니다!

hyun11732 3년 전 1

dir 값이 동서남북 1,2,3,4 순으로 문제에 정해져있습니다.

근데 님은 dir을 시계방향으로 설정해놓으셔서 return할때 문제가 생기는것 같아요!

axa1239 3년 전 0

댓글 감사드립니다!

dir 을 시계 방향 설정 (?) 무슨 소리이신지 잘모르겠습니다

문제에서 주어진 방향을 그대로 이용하면

방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

그대로 이용하면 된다는 말씀이신가여?

hyun11732 3년 전 1

네

const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };

이렇게 dx, dy값을 북동남서 방향으로 설정하셨는데

문제에는 동서남북으로 되있습니다.

그래서 마지막에 input 마지막줄 GOAL 방향까지 딱 맞아야하는데 님이 설정한 방향이랑 맞지않습니다.

예를들어 테스트 케이스에서

2 4 1

문제에 따르면 1번 방향은 동쪽인데 님 1번방향은 북쪽으로 설정되어있어서 결과값이 잘 안나오는것 같아요.

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

문제

문제

출처

ICPC

1726 틀렸습니다....

axa1239 4년 전 0

culture1123 4년 전 1

axa1239 4년 전 0

hyun11732 3년 전 1

axa1239 3년 전 0

hyun11732 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말