게시판 즐겨찾기
편집
드래그 앤 드롭으로
즐겨찾기 아이콘 위치 수정이 가능합니다.
bfs 예제 푸는데 틀린 부분좀 알려주세요ㅠㅠ (c언어,초보)
게시물ID : programmer_14236짧은주소 복사하기
작성자 : 간장맛닭둘기
추천 : 0
조회수 : 1105회
댓글수 : 5개
등록시간 : 2015/11/02 22:51:38
문제가 뭐냐면요
첫째 줄에는 바둑판의 가로, 세로 크기 N(5≤N≤15)이 입력되고 그 다음 줄부터 N줄 N개의 자료(0, 1, 2)가 입력된다. 여기서 0은 돌이 없는 곳, 1은 흰 돌, 2는 검은 돌을 의미한다.
흰 돌 한 점만을 놓아 흑 돌을 잡을 수 있는 지점을 찾아내는 것이다.
0 1
1 2  과 같이 구석에 몰린경우도  잡은걸로 합니다.
첫째 번째 줄에서 검은 돌을 따낼 수 있는 모든 지점의 수를 출력한다. 둘째 줄부터는 각 지점의 가로, 세로 좌표(x, y)를 x좌표가 작은 것을 먼저 출력 한다. 만일 x좌표가 같은 경우에는 y좌표가 작은 것을 먼저 출력한다. 또한 흰 돌 한 점을 놓아서 두 군데 이상 검은 돌을 따낼 수 있을 경우 좌표는 한 번만 출력한다. 만약 검은 돌을 따낼 수 있는 지점이 하나도 없으면 0을 출력한다.
 
1시간동안 풀었는데 뭐가 틀렸는지 모르겠어요ㅠ
어떻게 풀었냐면
 검은돌이 있는곳에서 상하좌우중 아무것도 없는 곳이 있을 때 그곳이 흰돌을 놓고 검은돌을 출발점으로 각각 bfs를 돌렸습니다. bfs가 돌때
흰돌이 있는곳은 가지 않게 하고 만약 0을 만나면 멈추게 했습니다.
입력
5
0 0 0 0 0
1 2 1 0 0
0 1 2 1 0
0 0 0 0 0
0 0 0 0 0

출력
2
2 1
3 4
 
입력
8
2 0 2 2 1 1 1 1
2 0 0 1 0 0 1 2
0 2 0 2 2 0 0 2
2 0 0 2 2 2 2 2
0 1 1 2 0 2 0 0
1 0 1 2 1 0 0 0
1 1 1 0 1 2 0 1
2 1 1 0 1 1 1 1
 
출력
0
이건 맞게 나오는데요
 
입력
7
1 2 1 1 1 2 1
2 1 0 0 2 0 2
0 0 2 1 1 1 1
0 1 2 1 1 1 0
0 1 0 1 2 0 1
2 2 0 1 2 2 1
0 1 1 2 2 2 1
출력
3
1 3
6 2
6 5
 
이게 틀리게 나와요
 
이거 읽어만 주셔도 감사하겠습니다. 시간이 없어서 성의 없게 설명한건 죄송합니다.
 
#include <stdio.h>
#include <queue>
using namespace std;
queue<int> Q;
int dy[4]={0,1,0,-1};                                        /방향데이터
int dx[4]={1,0,-1,0};
int cnt;                                                           /개수출력
int visit[16][16];                                             /visit배열
int b[16][16];                                                 /답출력할때 쓰는거

int a[16][16];                                                  /입력받는 배열
int n;

int bfs(int y,int x)                                      /bfs
{
int i;
int j;
int ty,tx;

for(i=1 ; i<=n ; i++)                                                     /visit배열 초기화
{
for(j=1 ; j<=n ; j++)
{
visit[i][j]=0;

}
}

Q.push(y);
Q.push(x);
visit[y][x]=1;


while(!Q.empty())
{
y=Q.front(); Q.pop();
x=Q.front(); Q.pop();
for(i=0 ; i<=3 ; i++)                                                                       /4방향 체크
{
ty=y+dy[i];
tx=x+dx[i];
if(ty>0 && ty<=n && tx>0 && tx<=n)
{
if(a[ty][tx]==2 && visit[ty][tx]==0)
{
Q.push(ty);
Q.push(tx);
visit[ty][tx]=1;
}
else if(a[ty][tx]==0)
{
return 1;                                                   /아무것도 없는 곳이 나왔을 때 bfs 멈춤
}
}
}
}


return 0;
}

void input(void)                                                                             
{
scanf("%d",&n);                                                                            /입력

int i,j,k;                                                                                         /반복문 변수
for(i=1 ; i<=n ; i++)                                                                         /입력
{
for(j=1 ; j<=n ; j++)
{
scanf("%d",&a[i][j]);
}
}

int ty,tx;                                                                                        /방향데이터 더할 때 쓰는 변수
for(i=1 ; i<=n ; i++)                                                                   
{
for(j=1 ; j<=n; j++)
{
if(a[i][j]==2)                                                                     /만약 검은 돌일때
{
for(k=0 ; k<=3 ; k++)                                                             /4방향체크
{
ty=i+dy[k];
tx=j+dx[k];
if(ty>0 &&  ty<=n && tx>0 && tx<=n && a[ty][tx]==0)        /아무것도 없는 곳이 있다면
{
a[ty][tx]=1;                                                          /흰돌을 놓고
if(bfs(i,j)==0)                                                         /bfs가 멈추지 않고 끝가지 돌면 답
{
b[ty][tx]=1;                                                     
}
a[ty][tx]=0;                                                        /bfs가 끝나면 다시 치운다
}
}
}
}
}
}
int main(void)
{
input();
int i,j;
for(i=1 ; i<=n ; i++)                                                                                /개수 체크
{
for(j=1 ; j<=n ; j++)
{
if(b[i][j]==1)
cnt++;
}
}
printf("%d\n",cnt);

for(i=1; i<=n ; i++)                                                                     /답출력
{
for(j=1 ; j<=n ; j++)
{
if(b[j][i]==1)
printf("%d %d\n",i,j);
}
}
return 0;
}




 
전체 추천리스트 보기
새로운 댓글이 없습니다.
새로운 댓글 확인하기
글쓰기
◀뒤로가기
PC버전
맨위로▲
공지 운영 자료창고 청소년보호