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 1
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 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); } } } } }