혼자서 dfs 하려다가 말아먹고 , 결국 다른분 코드 참고해서 만들었다.
문제는 아래와 같다.
원래 비숍이 놓일때마다 4방향의 대각선을 다 검색하는 방법을 사용하려고 했는데 , 시간초과가 나는 사람이 있다고도 하고
무식한것 같아서 방법을 찾다가, 체스판의 대각선을 2부분으로 나눠 푸는 것을 발견했다.
* 체스판을 N * N의 격자가 아니라, 2N 개의 대각선으로 바라보는 방법입니다.
대각선으로 체스판을 보게 되면 다음 두가지 이점이 있습니다.
1. 현재 대각선에서 비숍을 하나만 놓고 다음 대각선으로 이동하면 됩니다.
2. 현재 대각선의 어떤 위치에 비숍을 놓을 수 있는가의 검사는 반대 방향의 대각선에 비숍이 놓여졌는지를 확인하는것으로 O(1)에 수행할 수 있습니다.
이렇게 푸는 방법으로 MS가 0이 걸리는데 ,
내가 푼 방법은 MS 16이 걸린다. 아직 다른 방법으로 풀지 못했지만 그 소스는 같이 올려본다.
혹시 간단하게 이해시켜 주실 분이 있으면 댓글로 달아 주시는 것도 괜찮을 것 같다.
소스보기 (내가 푼 소스)
#include <stdio.h>
int board[11][11]={0},
chessman[25]={0},//체스가 놓여있는 자리 표시
cross[25],//대각선의 위치 표시
Max = -1,
boardSize=0,
result = 0;
void dfs(int row,int cal,int cnt,int flag){
//깊이우선탐색
if(cnt>Max)
//비숍의 갯수를 놓일때마다 최대값으로 갱신
Max = cnt;
if(cal > boardSize){
//열이 체스판의 크기를 넘어버리면 줄을 하나 늘림
row++;
if(flag==0){
//체스판의 대각선을 2부분으로 나눠 생각함
// \ 모양의 대각선이 1칸 걸쳐서 반복됨
if(row % 2 == 0)//줄이 짝수일 경우 대각선은 항상 2번째 부터 시작
cal = 2;
else
cal = 1;//아니면 1번째 부터 시작
}else if(flag==1){//다른 대각선 종류에 대해서 수행
if(row % 2 == 0)//줄이 짝수일경우 대각선은 항상 1번째 부터 시작
cal = 1;
else
cal = 2;//위와 마찬가지
}
}
if(row > boardSize)//줄이 체스판을 넘어가 버리면 끝
return;
if(chessman[row + cal] == 0 && cross[10 + row - cal] == 0 && board[row][cal] == 1){
//체스판에 놓일 비숍의 위치는 열+줄로 저장
//대각선은 열과 줄의 차이가 최대 10이니 10 + 줄 - 열로 저장
//체스판에 1로 표시된 곳이 비숍을 놓을 수 있는 장소
chessman[row + cal] = 1;
cross[10 + row - cal] = 1;
dfs(row, cal + 2, cnt + 1,flag);//대각선은 한칸씩 걸러서 위치하기 때문에 열을 2칸 증가, 비숍 수 증가
chessman[row + cal] = 0;//비숍을 안놨을때를 가졍하기 위함
cross[10 + row - cal] = 0;
}
dfs(row, cal + 2, cnt, flag);//비숍을 놓지 않고 재귀함수를 다시 돌림
return;
}
int main(){
scanf("%d",&boardSize);
for(int i=1; i<=boardSize; i++){
for(int j=1; j<=boardSize; j++){
scanf("%d",&board[i][j]);
}
}
dfs(1,1,0,0);//대각선을 두부분으로 나눈다고 했으니 dfs 재귀함수를 두번 수행해줘야함
result = Max;
Max = -1;
dfs(1,2,0,1);//마찬가지로 수행 후, 두 부분에서 비숍의 최대값들을 더해주면됨
result += Max;
printf("%d\n",result);
return 0;
}
상위 랭크된 정답자 소스 (이해가 안된다... 이해가가가가가가가각)
#include<iostream>
using namespace std;
int N;
int a[20][20];
int d1[30];
int max = -1;
int f(int n) {
if (n >= 2 * N - 1) {
return 0;
}
int max = -1;
int y = n < N ? n : N - 1;
int x = n < N ? 0 : n - (N - 1);
cout << y << ' ' << x << endl;
while (y >= 0 && x < N) {
if (a[y][x] == 1 && d1[x - y + N] == 0) {
d1[x - y + N] = 1;
int m = f(n + 2) + 1;
max = m > max ? m : max;
d1[x - y + N] = 0;
}
x++;
y--;
}
if (max < 0) max = f(n + 2);
return max;
}
int main(void) {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%d", &a[i][j]);
}
}
printf("%d\n", f(0) + f(1));
return 0;
}
'컴퓨터공학 > 알고리즘 _ 문제해결' 카테고리의 다른 글
206 Reverse Linked List [LeetCode] (0) | 2023.10.03 |
---|---|
11778 피보나치 수와 최대공약수 행렬 계산 방법 (0) | 2017.02.06 |
1003 번 문제 피보나치 함수 Dynamic Programming (0) | 2017.02.06 |
5704 팬그램 문자열 처리 문제 백준 (0) | 2017.01.29 |
백준 5026 박사 과정 문자열 처리 (0) | 2017.01.29 |