BOJ)1799 비숍 / 백트래킹

문제 : https://www.acmicpc.net/problem/1799

오답 (최초코드)

아래의 방식으로 풀이 시, 체스말이 서로 잡을 수 없는 위치하는 것은 맞다.

하지만, 체스말이 최대의 개수로 존재하는 것은 아니다.

#include <iostream> #include <algorithm> using namespace std; int n; int map[10][10]; int res[10][10] = { 0 }; bool func_check(int y, int x) { for (int i = y, j = x; i >= 0; i--, j--) { // 북서 if (res[i][j] != 0) return false; } for (int i = y, j = x; i >= 0; i--, j++) { // 북동 if (res[i][j] != 0) return false; } for (int i = y, j = x; j >= 0; i++, j--) { // 남서 if (res[i][j] != 0) return false; } for (int i = y, j = x; j < n; i++, j++) { // 남동 if (res[i][j] != 0) return false; } return true; } void func() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (map[i][j] != 0 && func_check(i, j)) { res[i][j] = 1; } } } } int main() { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> map[i][j]; } } func(); int r = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { r += res[i][j]; } } cout << r; }

(+추후수정 17.03.09)

정답

#include <iostream> #include <algorithm> using namespace std; int chess_size; int map[11][11]; int max_black = 0, max_white = 0; bool slash [22]; bool back_slash[22]; void black(int y, int x, int cnt) { max_black = max(max_black, cnt); if (x > chess_size) { //position이 체스의 끝부분에 도달하였을때, y++; x = (y % 2 == 0) ? 1 : 2; } if (y > chess_size) { return; } if (map[y][x] != 0 && slash[y + x] == false && back_slash[10+(y-x)] == false) { slash[y + x] = true; back_slash[10 + (y - x)] = true; black(y, x + 2, cnt+1); slash[y + x] = false; back_slash[10 + (y - x)] = false; } black(y, x + 2, cnt); } void white(int y, int x, int cnt) { max_white = max(max_white, cnt); if (x > chess_size) { //position이 체스의 끝부분에 도달하였을때, y++; x = (y % 2 == 0) ? 2 : 1; } if (y > chess_size) { return; } if (map[y][x] != 0 && slash[y + x] == false && back_slash[10 + (y - x)] == false) { slash[y + x] = true; back_slash[10 + (y - x)] = true; white(y, x + 2, cnt + 1); slash[y + x] = false; back_slash[10 + (y - x)] = false; } white(y, x + 2, cnt); } int main() { cin >> chess_size; for (int i = 1; i <= chess_size; i++) { for (int j = 1; j <= chess_size; j++) { cin >> map[i][j]; } } black(1, 2, 0); white(1, 1, 0); cout << max_black+max_white<<"\n"; }

1. white 위치에 비숍이 위치하였을 때, black 위치에는 영향을 끼치지 않는다.

   black 위치에 비숍이 위치하였을 때, white 위치에는 영향을 끼치지 않는다.

2.비숍이 위치한 곳을 기준으로 슬레쉬(/)방향과 백슬레쉬(＼) 방향은 추가로 비숍이 들어올 수 없다.

3.어느 위치에 존재하느냐에 따라, 비숍을 놓을 수 있는 수가 달라지므로, 탐색하며 최대의 값을 찾는다.

black과 white함수를 따로 나누어 놓았는데, 함수를 하나로 묶을 수 있을 것같다.

check(int y, int x, int cnt, int wb) 와 같은 형식으로 만들어 white일때는 wb=0, black일때는 wb=1

main 함수에서 check(1,1,0,0)과 check(1,2,0,1)의 합을 출력해준다.