문제가 뭐냐면요
첫째 줄에는 바둑판의 가로, 세로 크기 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;
}
글쓰기