글 읽기 - 솔직히 이해가안가는부분이있습니다

jerryprk 4년 전 0

모든구간에서 방향에따라 최소값이 나올 수 있으므로

해당문제를 3차원배열로 해서 풀어야 한다는것은 알겠습니다

BFS의 특성상 먼저 도착하는것이 가장 빠른 탐색수순이다 인데,

위 4방향의 가정이 추가되면 해당 부분에는 최소 3가지의 탐색수순이 나오는거아닌가요?
이것이 배제되어도 맞는 이유가 궁금하고

아래 소스에서 range와 visit을 비교하는 부분이있습니다

범위를 벗어나거나 벽이아니라면, 해당칸에 같은방향으로 왔던적이있다 를 판별하는데

둘을 동시에판별하면 틀리고

둘을 종속관계로 판별하게되면 맞다고합니다

range=true, visit=true
range=false, visit=true
range=true, visit=false
range=false, visit=false

3의 경우 들어가게되며, 이외의 모든부분은 탈락인데,

4의 경우를 배제하게된다해서 틀렸다고 나오는건가요?

#ifdef _DEBUG
#include "bits_stdc++.h"
#else
#include "bits/stdc++.h"
#endif
#pragma warning(disable:4996)
using namespace std;
#define MAX 101
#define INF 2147483647
int mab[MAX][MAX];
bool visit[MAX][MAX][4];
// 1동 2서 3남 4북
// 0   1   2   3
int xX[4] = { 1, -1, 0, 0 };
int yY[4] = { 0, 0, 1, -1 };

int h, w, low = INF;
typedef struct data {
	int y;
	int x;
	int ar;
	int cnt;
}Data;
Data st;
Data fs;
bool range(int y, int x) {
	if (y<0 || x<0 || y>h - 1 || x>w - 1 || mab[y][x])
		return false;
	else
		return true;
}
bool ran(int y, int x) {
	if (y<0 || x<0 || y>h - 1 || x>w - 1 || mab[y][x])
		return false;
	else
		return true;
}
bool chk(int y, int x, int ar) {
	if (y == fs.y && x == fs.x && ar == fs.ar)
		return true;
	else
		return false;
}
/*
void view() {
	for (int k = 0; k < 4; k++) {
		switch (k) {
		case 0:printf("[동]\n"); break;
		case 1:printf("[서]\n"); break;
		case 2:printf("[남]\n"); break;
		case 3:printf("[북]\n"); break;
		}
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				printf("%d ", visit[i][j][k]);
			}
			cout << endl;
		}
		cout << endl;
	}
	cout << endl;
}
*/
void solve() {
	queue <Data> q;
	q.push(st);
	visit[st.y][st.x][st.ar] = true;
	while (!q.empty()) {
		Data out = q.front(); q.pop();
		if (chk(out.y, out.x, out.ar)) {
			printf("%d", out.cnt);
			break;
		}
		for (int i = 0; i < 4; i++) {
			if (out.ar == i) {
				for (int k = 1; k <= 3; k++) {
					int ny = out.y + yY[i]*k;
					int nx = out.x + xX[i]*k;
					if (range(ny, nx)) {
						if (!visit[ny][nx][i]) {
							visit[ny][nx][i] = true;
							q.push({ ny,nx,i,out.cnt + 1 });
						}
					}
					/*
					if (range(ny, nx) && !visit[ny][nx][i]) {
						visit[ny][nx][i] = true;
						q.push({ ny,nx,i,out.cnt + 1 });
					}
					*/
					else 
						break;
				}
			}
			else if ((out.ar == 0 && i == 1) || (out.ar == 1 && i == 0)
				|| (out.ar == 2 && i == 3) || (out.ar == 3 && i == 2)) continue;
			else {
				if (!visit[out.y][out.x][i]) {
					visit[out.y][out.x][i] = true;
					q.push({ out.y,out.x,i,out.cnt + 1 });
				}
			}
		}
	}
}
int main() {
	scanf("%d %d", &h, &w);
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			scanf("%d", &mab[i][j]);
	scanf("%d %d %d", &st.y, &st.x, &st.ar);
	st.y--, st.x--, st.ar--, st.cnt = 0;
	scanf("%d %d %d", &fs.y, &fs.x, &fs.ar);
	fs.y--, fs.x--, fs.ar--;
	solve();
}

seico75 4년 전 0

3차원 공간으로 bfs 를 하는 것은 이해하신 것 같고, 이 경우 que 에 들어간 순서가 cnt 증가순으로만 유지할 수 있으면

찾는 결과가 최소값이라고 할 수 있겠죠.

아마도 동일한 공간에 도착했을 때 4방향에서 올 수 있으면 문제가 되지 않을까 생각하신 것 같은데,

위 소스는 1~3칸 움직이거나 좌우로 회전하는 것을 한번으로 해서 큐에 넣고 있어서 cnt 가 증가순을 유지합니다.

즉, x, y에서 출발하면 해당 방향으로 1~3으로 가는 경우, 좌턴, 우턴 이렇게 5가지 상황을 cnt 하나 증가시키면서 고려합니다. (벽이 없다는 전제일때....)

그래서 문제가 안되구요.

조건문은..

조건문 자체보다는 else 가 문제네요.

정답의 경우는 else 가 벽이나 밖으로 나가는 경우에 break 이나

오답의 경우는 방문한 경우도 break 되므로 오답이 됩니다.

한칸 갔는데 벽이나 밖으로 나가는 경우에는 두칸, 세칸을 안가도 되지만

한칸째가 이미 갔던데라고 두번째 세번째가 안가도 되는 것은 아니니까요..

제가 질문을 잘못이해했거나 답변이 이상하면 알려주세요.

jerryprk 4년 전 0

첫 질문에 대한답은 곰곰히생각해서! 같은 결론으로 이해했습니다!
같음을 한번더 직시하게해주셔서 감사하고

두번째 문제같은경우에는 질문을 적으면서 이해해버렷네요

다른방향에서 온 정보에있어서

한지점에서 먼저 교차로에 도착했을때, 다음 교차로에 도착하는 지점의 정보가

최솟값일수도잇음에도, 먼저방문된 적이있기때문에, 이부분은 진행이 되지 않으므로, 예외케이스가 존재할수 있다 군요

감사합니다

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

문제

문제

출처

ICPC

솔직히 이해가안가는부분이있습니다

jerryprk 4년 전 0

seico75 4년 전 0

jerryprk 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말