https://www.acmicpc.net/problem/1799
1799번: 비숍
첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로
www.acmicpc.net
코드설명
백트래킹 문제입니다.
문제를 처음봤을시 전체 체스판을 순회하면서 로직을 수행하면 될 것이라는 생각으로 코드를 작성했습니다.
문제에서 유의해야할점은
1.비숍을 둘 수 있더라도 비숍을 두지 않고 진행할때도 있어야합니다. 그렇게해야만, 완전탐색이 진행됩니다. 만약 비숍을 두지못할경우에만 진행을 하게된다면, 모든 경우를 탐색하지 못합니다.
if(arr[nowX][nowY] == 1 && visited[nowX][nowY] == false) {
//원상복구를 위한 메모리배열 사용시 메모리 초과.
BisshopVisited[nowX][nowY] = true; //실제로 비숍이 존재하는 위치 확인
setBisshop(nowX, nowY); //비숍을 두었을때 대각선 위치들을 모두 visited[][] true 로 설정해야합니다.
simulate(nowX, nowY + 1, cnt + 1);
BisshopVisited[nowX][nowY] = false;
calculateBisshop(nowX, nowY);
}
simulate(nowX, nowY + 1, cnt); //만약 비숍을 두지못한경우만 다음 칸으로 넘어가는것이 아닌 비숍을 둘 수 있더라도 두지않고 다음칸으로 이동합니다.
하지만, 이렇게 할경우 시간초과에 걸리게됩니다. ( 관련 코드 하단에 위치 )
시간초과가 나는 이유는, O( 2 ^ (N * N) ) 비숍을 놓을것인지 놓지않을것인지 총 N^N번을 고민하므로 시간복잡도가 이렇습 니다. 체스의 킈는 O(2 ^ ( 10 * 10 )) 는 O( 2^ 100) 입니다. 10억을 넘어가므로 시간초과가 납니다.
시간초과를 해결하기 위해서는 다른 방식으로 해결이 필요합니다.
비숍은 대각선으로만 움직일 수 있습니다. 즉, 체크무늬모양의 타일이 존재한다고할때 (0,0)을 하얀색 타일이라고한다면, (0,1) 은 검은색 타일이라고 할 수 잇습니다.
이를 활용해 각 하얀타일을 최대한 많이 선택하는경우와 검은타일을 최대한 많이 선택하는경우로 나누어서 구합니다.
그렇다면 시간복잡도는 O( 2 ^ ( N/2 * N/2) + 2 ^ (N/2 * N/2)) 입니다. 시간복잡도가 훨씬 줄어드므로 성공합니다.
코드
비숍을 하얀칸과 검은칸으로 나눈경우 시간복잡도는 O( 2 ^ ( N/2 * N/2) + 2 ^ (N/2 * N/2))
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N;
public static int[][] arr;
public static boolean[][] visited;
public static boolean[][] BisshopVisited;
//좌상, 우상, 우하, 좌하
public static int[] dx = {-1,-1,1,1};
public static int[] dy = {-1,1,1,-1};
public static int answer = 0;
public static int whiteCnt = 0, blackCnt = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new int[N][N];
BisshopVisited = new boolean[N][N];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
whiteSearchSimulate(0, 0, 0, 0);
blackSearchSimulate(0, 0, 1, 0);
System.out.println(whiteCnt + blackCnt);
}
public static void whiteSearchSimulate(int level, int r, int c, int cnt) {
if(c >= N) {
r = r + 1;
if( r % 2 == 0) {
c = 0;
} else {
c = 1;
}
}
// if(level >= N * N) {
// return ;
// }
if(r >= N) {
whiteCnt = Math.max(whiteCnt, cnt); //종료시점에검사.
return ;
}
if(arr[r][c] == 1 && checkAvailable(r, c) == true) {
BisshopVisited[r][c] = true;
whiteSearchSimulate(level + 1, r, c + 2, cnt + 1);
BisshopVisited[r][c] = false;
}
whiteSearchSimulate(level + 1, r, c + 2, cnt);
}
public static void blackSearchSimulate(int level, int r, int c, int cnt) {
if(c >= N) {
r = r + 1;
if( r % 2 == 0) {
c = 1;
} else {
c = 0;
}
}
// if(level >= N * N) {
// return ;
// }
if(r >= N) {
blackCnt = Math.max(blackCnt, cnt); //종료시점에검사.
return ;
}
if(arr[r][c] == 1 && checkAvailable(r, c) == true) {
BisshopVisited[r][c] = true;
blackSearchSimulate(level + 1, r, c + 2, cnt + 1);
BisshopVisited[r][c] = false;
}
blackSearchSimulate(level + 1, r, c + 2, cnt);
}
public static boolean checkAvailable(int r, int c) {
for(int dir = 0; dir < 4; dir ++) {
int nr = r + dx[dir];
int nc = c + dy[dir];
while(true) {
if(nr < 0 || nr >= N || nc < 0 || nc >= N) break;
if(BisshopVisited[nr][nc] == true) return false; //해당 대각선을 확인했을떄 이미 다른 비숍이 존재한다면 놓지못합니다.
nr = nr + dx[dir];
nc = nc + dy[dir];
}
}
return true;
}
}
방문처리를 간단하게 바꿔본 코드지만 시간초과가 여전함 시간복잡도는 O( 2 ^ (N * N) )
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N;
public static int[][] arr;
public static boolean[][] visited;
public static boolean[][] BisshopVisited;
//좌상, 우상, 우하, 좌하
public static int[] dx = {-1,-1,1,1};
public static int[] dy = {-1,1,1,-1};
public static int answer = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new int[N][N];
BisshopVisited = new boolean[N][N];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
simulate(0, 0, 0);
System.out.println(answer);
}
public static void simulate(int nowX, int nowY, int cnt) {
if(nowX >= N-1 && nowY >= N) {
answer = Math.max(answer, cnt);
return ;
}
if(nowY >= N) {
nowX += 1;
nowY = 0;
}
if(arr[nowX][nowY] == 1 && checkAvailable(nowX, nowY) == true) {
BisshopVisited[nowX][nowY] = true; //실제로 비숍이 존재하는 위치 확인
simulate(nowX, nowY + 1, cnt + 1);
BisshopVisited[nowX][nowY] = false;
}
simulate(nowX, nowY + 1, cnt);
}
public static boolean checkAvailable(int startX, int startY) {
for(int dir=0;dir<4;dir++) {
int nx = startX + dx[dir];
int ny = startY + dy[dir];
while(true) {
if(nx < 0 || nx >= N || ny < 0 || ny >= N) break;
if(BisshopVisited[nx][ny] == true) return false;
nx += dx[dir];
ny += dy[dir];
}
}
return true;
}
}
시간초과가 나는 코드 시간복잡도는 O( 2 ^ (N * N) )
10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N;
public static int[][] arr;
public static boolean[][] visited;
public static boolean[][] BisshopVisited;
public static int answer = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new int[N][N];
visited = new boolean[N][N];
BisshopVisited = new boolean[N][N];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
simulate(0, 0, 0);
System.out.println(answer);
}
public static void simulate(int nowX, int nowY, int cnt) {
if(nowX >= N-1 && nowY >= N) {
answer = Math.max(answer, cnt);
return ;
}
if(nowY >= N) {
nowX += 1;
nowY = 0;
}
if(arr[nowX][nowY] == 1 && visited[nowX][nowY] == false) {
//원상복구를 위한 메모리배열 사용시 메모리 초과.
BisshopVisited[nowX][nowY] = true; //실제로 비숍이 존재하는 위치 확인
setBisshop(nowX, nowY); //비숍을 두었을때 대각선 위치들을 모두 visited[][] true 로 설정해야합니다.
simulate(nowX, nowY + 1, cnt + 1);
BisshopVisited[nowX][nowY] = false;
calculateBisshop(nowX, nowY);
}
simulate(nowX, nowY + 1, cnt);
}
public static void setBisshop(int startx, int starty) {
int originStartX = startx;
int originStartY = starty;
visited[startx][starty] = true;
//우상 대각선 처리
while(true) {
int nx = startx - 1;
int ny = starty + 1;
if( nx < 0 || nx >= N || ny < 0 || ny >= N) break;
if( arr[nx][ny] == 1 ) {
visited[nx][ny] = true;
}
startx -= 1;
starty += 1;
}
startx = originStartX;
starty = originStartY;
//좌하 대각선 처리
while(true) {
int nx = startx + 1;
int ny = starty - 1;
if( nx < 0 || nx >= N || ny < 0 || ny >= N) break;
if( arr[nx][ny] == 1 ) {
visited[nx][ny] = true;
}
startx += 1;
starty -= 1;
}
startx = originStartX;
starty = originStartY;
//좌상 대각선 처리
while(true) {
int nx = startx - 1;
int ny = starty - 1;
if( nx < 0 || nx >= N || ny < 0 || ny >= N) break;
if( arr[nx][ny] == 1 ) {
visited[nx][ny] = true;
}
startx -= 1;
starty -= 1;
}
startx = originStartX;
starty = originStartY;
//우하 대각선 처리
while(true) {
int nx = startx + 1;
int ny = starty + 1;
if( nx < 0 || nx >= N || ny < 0 || ny >= N) break;
if( arr[nx][ny] == 1 ) {
visited[nx][ny] = true;
}
startx += 1;
starty += 1;
}
}
public static void calculateBisshop(int startx, int starty) {
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
visited[i][j] = false;
}
}
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
if(BisshopVisited[i][j] == true) {
setBisshop(i, j);
}
}
}
}
}