-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
PQ 말고 그냥 queue로 하면 틀린것인가요??
21.03.04 02:50 작성 조회수 186
0
안녕하세요 선생님
저는 이 문제에서 왼쪽과 위쪽 우선순위를 그냥 for loop 돌 때 dx dy 순서를 그렇게 짜면 되겠다 해서
밑에 코드처럼 짰습니다 저렇게 되면 답이 맞지 않는 것인가요??
(맥을 이용중이라 채점 프로그램을 쓰지 못하고 있네요 ㅠㅠ)
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
int map[30][30];
int time=0, size=2, n, cnt=0;
int dx[4]={0,-1,1,0};
int dy[4]={-1,0,0,1};
struct Loc{
int x;
int y;
Loc(int a, int b){
x=a;
y=b;
}
};
queue<Loc> Q;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&map[i][j]);
if(map[i][j]==9) {
Q.push(Loc(i,j));
map[i][j]=0;
}
}
}
while(!Q.empty()){
Loc tmp = Q.front();
Q.pop();
for(int i=0;i<4;i++){
int xx = tmp.x+dx[i];
int yy = tmp.y+dy[i];
if(xx>=1 && xx<= n && yy>=1 && yy<=n && map[xx][yy]<=size && map[xx][yy]!=0){
Q.push(Loc(xx,yy));
cnt++;
if(map[xx][yy]<size){
if(size==cnt) size+1;
map[xx][yy]=0;
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(map[i][j]!=0) printf("%no");
}
}
printf("%d",&cnt);
return 0;
}
답변을 작성해보세요.
1
김태원
지식공유자2021.03.05
안녕하세요^^
그냥 큐로는 안됩니다. 우선순위큐를 써야 합니다.
위 코드는 문제에 있는 입력예제의 출력이 5가 나옵니다. 10이 정답인데 5가 나오는 이유가 뭔지 스스로 생각해 보세요.
심바는 한 위치에서 4방향으로 퍼져나가는 것이 아니라
1번 위치에서 가장 가까운 토끼가 있는 2번 위치로 이동하고, 2번 위치에서 가장 가까운 토끼를 검색해 그 위치로 이동하고 ...
이런식으로 계속 이동하는 것입니다.
예리얼
질문자2021.03.09
선생님 !!
선생님이 올려주신 코드로 백준에서 아기상어 문제에 제출을 해봤더니
틀렸습니다가 나왔네요.. 완전히 같은 문제 같은데... 어떤게 잘못된걸까요??
답변 1