글 읽기 - 문제가 어렵네요.ㅜㅜ

greeneye 6년 전 0

현재 위치에서 bfs를 돌려서 갈 수 있는 방향을 찾습니다.
갈 수 있는 방향까지 가는데 trun 횟수와 이동거리를 계산해서 넣어줍니다.

- visit 함수를 3차원으로 하여 맵 + 방향에 따른 방문을 기록 하였습니다.

- 가는 방향이 3을 초과할면 회수를 1 + 해줍니다.

어디서 부터 잘 못 된 걸까요?

/*

*/

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define SIZE 105 // 105

int map[SIZE][SIZE];
int visit[SIZE][SIZE][5];
struct points {
	int x, y, dir, depth, conti;
};
int x, y, nx, ny, dir, depth;
int dx[] = { 0, 0,0,1,-1 };
int dy[] = { 0, 1,-1,0,0 };
int M, N;
int startX, startY, startDir, endX, endY, endDir, conti;
queue<points> que;

void problemIn() {
	cin >> M >> N;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	cin >> startX >> startY >> startDir >> endX >> endY >> endDir;
	startX -= 1;
	startY -= 1;
	endX -= 1;
	endY -= 1;
	visit[startX][startY][startDir] = 1;
	que.push({ startX, startY, startDir, 0, 1 });
}

/*

*/
int turn_num(int curDir, int postDir) {
	if (curDir == 1) {
		if (postDir == 2) return 1; // 180 돌아도 한번으로 셈?
		else if (postDir == 3) return 1;
		else if (postDir == 4) return 1;
		else if (postDir == 1) return 0;
	}
	if (curDir == 2) {
		if (postDir == 1) return 1;
		else if (postDir == 3) return 1;
		else if (postDir == 4) return 1;
		else if (postDir == 2) return 0;
	}
	if (curDir == 3) {
		if (postDir == 4) return 1;
		else if (postDir == 1) return 1;
		else if (postDir == 2) return 1;
		else if (postDir == 3) return 0;
	}
	if (curDir == 4) {
		if (postDir == 3) return 1;
		else if (postDir == 1) return 1;
		else if (postDir == 2) return 1;
		else if (postDir == 4) return 0;
	}
}

int bfs() {

	while (!que.empty()) {
		x = que.front().x;
		y = que.front().y;
		dir = que.front().dir;
		depth = que.front().depth;
		conti = que.front().conti;
		que.pop();

		if (x == endX && y == endY) {
			return depth + turn_num(dir, endDir);
		}

		for (int i = 1; i <= 4; i++) {
			nx = x + dx[i];
			ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
				if (map[nx][ny] == 0 && visit[nx][ny][dir] == 0) {
					visit[nx][ny][dir] = 1;
					int ret = turn_num(dir, i);
					if (ret == 0) {
						conti++;
						if (conti > 3) {
							ret += 1;
							conti = 1;
						}
					}
					else {
						conti = 1;
					}
					que.push({ nx,ny,i,depth + ret + ((dir==i)?0:1), conti});
				}
			}
		}
	}
}

int main() {
	problemIn();
	int ans = bfs();
	cout << ans << endl;
}

jh05013 6년 전 1

180도 회전은 2번의 명령이 필요합니다.

greeneye 6년 전 1

댓글 감사합니다 ㅜㅜ

180도 회전에 대해서 2회로 처리했음에도, 9%에서 틀립니다가 나옵니다ㅜㅜ

음

한번 다시 풀어보도록 할게요!!!

greeneye 6년 전 0

다른 분 코드 참조해서 해결했습니다.

위 코드에서 변경하지 않고, 코드 새로 짰습니당

/*
갈 수 있는 곳에 대한 처리를 명확하게 하는 것이 필요합니다.
그 방향으로 1,2,3 칸 갈 수 있으면 방향과 그 칸을 q 에 넣어주고 계산을 둘러보면 됩니다. 
*/

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct point {
	int x, y, dir, cnt;
};

int x, y, nx, ny, dir, cnt;
int dx[] = { 0, 0,0,1,-1 };
int dy[] = { 0, 1,-1,0,0 };
#define SIZE 105 // 105
int map[SIZE][SIZE];
int visit[SIZE][SIZE][5];
int startX, startY, endX, endY, startDir, endDir;
int M, N;
queue<point> que;


void problemIn() {
	cin >> M >> N;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	cin >> startX >> startY >> startDir >> endX >> endY >> endDir;
	startX -= 1;
	startY -= 1;
	endX -= 1;
	endY -= 1;

	visit[startX][startY][startDir] = 1;
	que.push({ startX, startY, startDir, 0 });
}

int opp(int n) {
	if (n == 1) return 2;
	else if (n == 2) return 1;
	else if (n == 3) return 4;
	else return 3;
}

int bfs() {

	while (!que.empty()) {
		x = que.front().x;
		y = que.front().y;
		dir = que.front().dir;
		cnt = que.front().cnt;
		que.pop();

		if (x == endX && y == endY && dir == endDir) {
			return cnt;
		}

		for (int i = 1; i <= 3; i++) {  // 그 방향으로 갈 수 있는 곳은 cnt 변화 없이 que 에 넣습니다. 
			nx = x + dx[dir] * i;
			ny = y + dy[dir] * i;
			if (nx < 0 || ny < 0 || nx >= M || ny >= N) break; // 맵을 벗어나면
			if (map[nx][ny]) break; // 벽이면
			if (visit[nx][ny][dir]) continue; // 다음 것 조사하도록 넘어갑니다.
			visit[nx][ny][dir] = 1;
			que.push({ nx,ny,dir,cnt + 1 });
		}

		for (int i = 1; i <= 4; i++) { // 동 서 남 북 으로 턴해서 갈 수 있는 곳은 cnt+1 을 하고 que에 넣습니다.
			if (i == dir ) continue; // 동쪽을 바라보고 있으면 그냥, 서쪽을 바라보고 있으면 그냥 왜 반대쪽도 그냥 넘어가지?
			if (visit[x][y][i]) continue; // 왔던 길이면, 패스
			visit[x][y][i] = 1;
			if (i == opp(dir)) {
				que.push({ x,y,i,cnt + 2 });
			}
			else {
				que.push({ x,y,i,cnt + 1 });
			}
		}
	}
	return 0;
}

int main() {
	problemIn();
	int ans = bfs();
	cout << ans << endl;
	return 0;
}

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

문제

문제

출처

ICPC

문제가 어렵네요.ㅜㅜ

greeneye 6년 전 0

jh05013 6년 전 1

greeneye 6년 전 1

greeneye 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말