개발자 톡
BFS로 풀어볼려했는데, 5개정도가 통과가 안되네요,, 피드백 부탁합니다!
- 등록일
- 2025-02-07 14:26:13
- 조회수
- 57
- 작성자
- well77
#include <stdio.h>
#define Max_Size 1001
int di[4] = {-1,1,0,0};
int dj[4] = {0,0,-1,1};
enum name{
Ghost = 0,
Person = 1,
Exit = 2
};
typedef struct queue{
int i_front;
int j_front;
int i_rear;
int j_rear;
int i_data[Max_Size];
int j_data[Max_Size];
}Queue;
char map[Max_Size][Max_Size];
int index_i[3][Max_Size];
int index_j[3][Max_Size];
int RowSize,ColSize;
int ghost_Cnt;
void find_index();
int BFS_shortest(int starti,int startj,char target){
int distance[Max_Size][Max_Size];
memset(distance, -1, sizeof(distance));
int curri,currj;
int nexti,nextj;
distance[starti][startj] = 0;
Queue q;
q.i_rear = -1;
q.i_front = -1;
q.j_rear = -1;
q.j_front = -1;
q.i_data[++q.i_rear] = starti;
q.j_data[++q.j_rear] = startj;
while(q.i_front < q.i_rear && q.j_front < q.j_rear){
curri = q.i_data[++q.i_front];
currj = q.j_data[++q.j_front];
for(int i = 0; i < 4; ++i){
nexti = curri + di[i];
nextj = currj + dj[i];
if (nexti < 1 || nexti > RowSize || nextj < 1 || nextj > ColSize) {
continue;
}
switch (target){
case 'G':
if (distance[nexti][nextj] == -1 ){
distance[nexti][nextj] = distance[curri][currj] + 1;
q.i_data[++q.i_rear] = nexti;
q.j_data[++q.j_rear] = nextj;
}
break;
case 'N':
if (distance[nexti][nextj] == -1 && map[nexti][nextj] != '#' ){
distance[nexti][nextj] = distance[curri][currj] + 1;
q.i_data[++q.i_rear] = nexti;
q.j_data[++q.j_rear] = nextj;
}
break;
}
}
}
return distance[index_i[Exit][0]][index_j[Exit][0]];
}
int main(void)
{
int i_person,j_person;
int ghostdis[Max_Size] = {0};
scanf("%d %d",&RowSize,&ColSize);
for (int i=1; i <= RowSize; ++i){
for (int j=1; j <= ColSize; ++j){
scanf(" %c",&map[i][j]);
}
}
find_index();
i_person = index_i[Person][0];
j_person = index_j[Person][0];
int Person_dis= BFS_shortest(i_person,j_person,'N');
if (Person_dis == -1){
printf("No");
return 0; //도달 불가능 하다면 No
}
for(int num = 0; num < ghost_Cnt; ++num){
ghostdis[num] = BFS_shortest(index_i[Ghost][num],index_j[Ghost][num],'G');
}
if ((ghostdis[0] == 0) && (Person_dis != -1)) {
printf("Yes");
return 0;
}
for (int i = 0; i < ghost_Cnt; ++i){
if (ghostdis[i] <= Person_dis){
printf("No");
return 0;
}
}
printf("Yes");
return 0;
}
void find_index(){
int tempG_i = -1;
int tempG_j = -1;
int tempN_i = -1;
int tempN_j = -1;
int tempD_i = -1;
int tempD_j = -1;
for (int i=1; i <= RowSize; ++i){
for (int j=1; j <= ColSize; ++j){
switch (map[i][j]){
case 'G':
index_i[Ghost][++tempG_i] = i;
index_j[Ghost][++tempG_j] = j;
ghost_Cnt++;
break;
case 'D':
index_i[Exit][++tempD_i] = i;
index_j[Exit][++tempD_j] = j;
break;
case 'N':
index_i[Person][++tempN_i] = i;
index_j[Person][++tempN_j] = j;
break;
}
}
}
}