[백준] 1799번 비숍

생각

체스에서 비숍은 대각선으로 만 이동할 수 있다. 체스판과 비숍을 놓을 수 있는 위치(1)가 주어질 때,
가장 많은 비숍을 놓을 수 있는 수를 구하시오

처음 생각

맵에서 비숍을 가장 많이 놓아야하는 문제이므로 DFS를 진행하면서 안 될 경우 백트래킹을 진행하면 된다고 생각하였다.

다음 생각

비숍을 놓을 수도 안 놓을 수도있는 자리가 1로 주어지고 아예 못놓는 자리가 0으로 주어지는데 반대로 생각해서 틀렸습니다를 얻었다.

다다음 생각

다시 1과 0의 판단을 바꿔준 후, 제출하였지만 시간 초과를 얻었다. 우선 시간 초과를 해결해보기위해서 기존의 배열을 다보는 형식을 처음에 입력 받을 때 놓을 수 있는 위치만 List에 좌표값을 넣어주어 놓을 수 없는 위치는 배제하고 살펴보았다.

▶ 좌,우 상향 대각선만 보면 되므로, 0부터 현 Index까지 반복문을 돌면서 x,y좌표와 현 좌표를 뺀 값을 절대를 취해서 같을 경우 대각선에 있다고 판단하였다.(코드를 보면 이해가 될 것 같습니다)

▶ 시간 초과를 얻었다.

다다다음 생각

생각을 하다 비숍이 이동할 수 있는 경로는 대각선 뿐이므로 현재 칸과 그 옆에있는 칸은 서로 독립관계가 된다.(영향을 끼치지 않는다) 따라서 DFS를 따로따로 진행해도 된다.

▶ 모든 칸을 동시에 진행할 경우는 경우의 수가 급격히 많아지지만 각각 볼경우는 달라진다. 예를들어 놓을 수 있는 칸이 1 1 이렇게 두개가 있다면 한 번에 DFS를 진행할 경우 경우의 수는 0을 안 놓는다로 하였을 때, (0 0) (0 1) (1 0) (1 1) 네가지가 되지만 둘은 인접한 칸이므로 대각선만 영향을 끼치기 때문에 독립 관계로 보면, (0)(1) + (0)(1) 이 된다. 따라서 2개의 경우에는 수가 같지만 숫자가 늘어날 경우 전자인 한 번에 진행하는 경우는 그 수가 급격히 증가해서 시간 초과를 받게된 것이다!!

다다다다음 생각

List를 만들어둔 김에 그대로 쓰기로 생각하여 독립 관계를 같는 대각선끼리 리스트를 분리해서 넣어주었다.

방안

1) 원래 진행했던 방식이 시간 초과가 걸린 경우, 종이에 써보면서 어떤걸 줄일 수 있을 까를 생각해보는게 좋은 방법같다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer;   class Main {     static int[][] arr,divide;     static int n,t;     static List<ArrayList<Pair>> list;     public static void main(String[] args) throws IOException{         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         n = Integer.parseInt(br.readLine());         arr = new int[n][n];         divide = new int[n][n];         list = new ArrayList<>();         list.add(new ArrayList<>()); list.add(new ArrayList<>());         for(int i=0;i<n;i++) {             StringTokenizer st = new StringTokenizer(br.readLine());             for(int j=0;j<n;j++) {                 arr[i][j] = Integer.parseInt(st.nextToken());                 // 대각 별로 나눠서 보자.                 if(i%2==0) {                     if(j%2==0) divide[i][j] = 1;                 }else {                     if(j%2!=0) divide[i][j] = 1;                 }                 if(arr[i][j]==1) {                     if(divide[i][j]==0)    list.get(0).add(new Pair(i,j));                     else list.get(1).add(new Pair(i,j));                 }             }         }         int result = 0;         t = 0;         if(list.get(0).size()!=0)             solve(list.get(0).get(0).x,list.get(0).get(0).y,0,0,0);         result=t; t = 0;         if(list.get(1).size()!=0)             solve(list.get(1).get(0).x,list.get(1).get(0).y,0,0,1);                 result+=t;         System.out.println(result);     }          private static void solve(int x,int y,int sum,int idx,int d) {         // 놓을 수 있다면         if(check(x,y,idx,d)) {             // 놓고 다음 꺼 보기             arr[x][y] = -1;             int tSum = sum+1;             t = Math.max(t, tSum);             if(idx+1<list.get(d).size())                 solve(list.get(d).get(idx+1).x,list.get(d).get(idx+1).y,tSum,idx+1,d);         }         // 먼저 도착한 x,y가 위쪽이니 사용안한다는 의미로 3         // 놓지 않고 다음 꺼 보기         arr[x][y] = 1;         if(idx+1<list.get(d).size())             solve(list.get(d).get(idx+1).x,list.get(d).get(idx+1).y,sum,idx+1,d);     }          // 위에서 부터 내려가는 것이니 위 쪽만 체크하면 된다.     private static boolean check(int x,int y,int idx,int d) {         for(int i=0;i<idx;i++) {             int tx = list.get(d).get(i).x;             int ty = list.get(d).get(i).y;             if(Math.abs(tx-x)==Math.abs(ty-y)) {                 if(arr[tx][ty]==-1) return false;             }         }         return true;     }          static class Pair{         int x,y;         public Pair(int x,int y) {             this.x = x;             this.y = y;         }     } } Colored by Color Scripter

cs