글 읽기 - 어느 부분이 잘못되었는지 잘 모르겠습니다..

wondy1128 7년 전 0

BFS로 구현하였고,

1. 맵안에 존재하며 - 막히지 않고( == 0), 방문하지 않았다면( !visited) Q에 넣는다.

2. 현재 위치에서 모든 방향을 탐색하지 않았다면( !dirVisit) 모든 방향을 큐안에 넣는다.

이때(2.) 180도 방향은 움직임 +2, +-90도 방향은 +1 로 설정하여 큐에 넣는다.

이 두가지로 코드를 작성하였습니다.

테스트케이스를 몇가지 만들어 보지는 않았지만, 어느부분이 잘못 생각한 부분인지 잘 모르겠습니다.

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;

VVI imap;
VVI visited;
VVI dirVisit;
int dir[5][2] = { {0,0}, {0,1} , {0,-1}, {1,0} , {-1,0} };

struct info{
	int r;
	int c;
	int d;
	int count;
	info(int ri, int ci, int di, int cnti)
		: r(ri), c(ci), d(di), count(cnti){}
};

int main(){
	int row, col;
	scanf("%d %d", &row, &col);
	imap = VVI(row, VI(col, 0) );
	visited = VVI(row, VI(col, 0) );
	dirVisit = VVI(row, VI(col, 0) );

	for(int r = 0 ; r < row ; r++){
		for(int c = 0 ; c < col ; c++){
			scanf("%d", &imap[r][c]);
		}
	} // input map

	int sr, sc, sd;
	int fr, fc, fd;
	scanf("%d %d %d", &sr, &sc, &sd);
	scanf("%d %d %d", &fr, &fc, &fd);

	sr--, sc--, fr--, fc--;

	info s(sr, sc, sd, 0);
	queue<info> q;
	q.push(s);

	while(!q.empty()){ // BFS
		info here = q.front(); q.pop();
		
		if(here.r == fr && here.c == fc && here.d == fd){
			printf("%d",here.count);
			return 0;
		} // 무조건 갈 수 있으므로 무조건 답나옴.
		for(int i = 1 ; i <= 4 ; i++){
			if(i == here.d){
				bool isImpossible = false;
				int tr = here.r;
				int tc = here.c;
				while(1){
					if(isImpossible) break;
					tr += dir[i][0];
					tc += dir[i][1];

					if(0 <= tr && tr < row && 0 <= tc && tc < col){ // 1 큐 넣기 조건
						if(!visited[tr][tc] && imap[tr][tc] == 0){
							visited[tr][tc] = true;
							info t(tr,tc,i,here.count+1);
							q.push(t);
						}else{
							isImpossible = true;
						}
					}else{
						isImpossible = true;
					}
				} 

				// direction 
				if(!dirVisit[here.r][here.c]){ // 큐 넣기 조건 2
					info t(here.r ,here.c, here.d, here.count+1);
					switch(here.d){
					case 1: 
						t.d = 3; q.push(t);
						t.d = 4; q.push(t);
						t.d = 2; t.count++; q.push(t);
						break;
					case 2:
						t.d = 3; q.push(t);
						t.d = 4; q.push(t);
						t.d = 1; t.count++; q.push(t);
						break;
					case 3:
						t.d = 1; q.push(t);
						t.d = 2; q.push(t);
						t.d = 4; t.count++; q.push(t);
						break;
					case 4:
						t.d = 1; q.push(t);
						t.d = 2; q.push(t);
						t.d = 3; t.count++; q.push(t);
						break;
					}
					dirVisit[here.r][here.c] = true;
				}
			}
		}

	}
	return 0;
}

wondy1128 7년 전 0

문제를제대로 읽지 않아서... 잘못 작성한 부분 수정하고서 9% -> 27% 로 바뀌는데 어떤부분이 더 잘못되었을 까요..

#include<cstdio>
#include<vector>
#include<queue>
#define MAX 111
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;


VVI imap;
bool visited[5][MAX][MAX];
int dir[5][2] = { {0,0}, {0,1} , {0,-1}, {1,0} , {-1,0} };

struct info{
	int r;
	int c;
	int d;
	int count;
	info(int ri, int ci, int di, int cnti)
		: r(ri), c(ci), d(di), count(cnti){}
};

int main(){
	int row, col;
	scanf("%d %d", &row, &col);
	imap = VVI(row, VI(col, 0) );

	for(int r = 0 ; r < row ; r++){
		for(int c = 0 ; c < col ; c++){
			scanf("%d", &imap[r][c]);
		}
	} // input map

	int sr, sc, sd;
	int fr, fc, fd;
	scanf("%d %d %d", &sr, &sc, &sd);
	scanf("%d %d %d", &fr, &fc, &fd);

	sr--, sc--, fr--, fc--;

	info s(sr, sc, sd, 0);
	queue<info> q;
	q.push(s);
	visited[sd][sr][sc] = true;
	while(!q.empty()){ // BFS
		info here = q.front(); q.pop();
		
		if(here.r == fr && here.c == fc && here.d == fd){
			printf("%d\n",here.count);
			break;
		} // 무조건 갈 수 있으므로 무조건 답나옴.
		switch(here.d){
		case 1:case 2: // 3 4
			if(!visited[3][here.r][here.c]){
				visited[3][here.r][here.c] = true;
				info t(here.r, here.c, 3, here.count+1);
				q.push(t);
			}
			if(!visited[4][here.r][here.c]){
				visited[4][here.r][here.c] = true;
				info t(here.r, here.c, 4, here.count+1);
				q.push(t);
			}
			break;// 3 4
		case 3:case 4: // 1 2
			if(!visited[1][here.r][here.c]){
				visited[1][here.r][here.c] = true;
				info t(here.r, here.c, 1, here.count+1);
				q.push(t);
			}
			if(!visited[2][here.r][here.c]){
				visited[2][here.r][here.c] = true;
				info t(here.r, here.c, 2, here.count+1);
				q.push(t);
			}
			break;// 1 2
		}

		for(int i = 1 ; i <= 4 ; i++){
			if(i == here.d){
				bool isImpossible = false;
				int tr = here.r;
				int tc = here.c;
				int k = 0;
				while(1){
					
					tr += dir[i][0];
					tc += dir[i][1];
					
					if(0 <= tr && tr < row && 0 <= tc && tc < col){
						if(!visited[i][tr][tc] && imap[tr][tc] == 0){
							visited[i][tr][tc] = true;
							info t(tr, tc, i, here.count+1);
							q.push(t);
						}else{
							isImpossible = true;
						}
					}else{
						isImpossible = true;
					}
					k++;
					if(k==3 || isImpossible) break; // 문제,......제대로 안읽네...
				}
			}
		}

		
	}
	return 0;
}
// 9 % 틀렸습니다.
// 27% 틀렸습니다.

wondy1128 7년 전 0

해결했습니다... 문제 제대로 안읽었네요...정말로;;

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

문제

문제

출처

ICPC

어느 부분이 잘못되었는지 잘 모르겠습니다..

wondy1128 7년 전 0

wondy1128 7년 전 0

wondy1128 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말