[백준] 3085번 사탕 게임

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q3000/Q3085.java

사탕들이 주어진다. 인접한 사탕을 교환했을 때, 사탕이 연이어서 있는 최대 개수를 출력하시오.

처음 생각

완전 탐색 문제이다. 배열 탐색을 왼쪽 위에서부터 한다고 생각하면, 각 좌표별로 오른쪽과 아래쪽으로만 사탕 교환을 해준다면 전부 바꾼거랑 같기 때문에 사탕별로 상 하 좌 우를 전부 바꿔주지 않아도 된다.

다음 생각

사탕을 교환할 때 범위를 넘지 않도록 행의 교환일경우 x-1까지 열의 교환일 경우 y-1 까지만 교환을 하도록 해주었다.

다다음 생각

먼저 행(아래쪽)을 바꾸고나서 배열을 체크해서 사탕이 연속된 가장 큰 개수를 찾아주었다. 그 다음에 열(오른쪽)을 바꾸고나서 마찬가지로 배열을 체크하여 사탕이 연속된 가장 큰 개수를 찾아주었다.

▶ 체크를 할 때 N이 최대 50이므로 크지가 않아 배열을 처음부터 끝까지로 해서 탐색해도 상관은 없지만 오른쪽을 바꿔주면 해당 행과 바뀌는 열 2개만 탐색하면 된다. 반대로 아래를 바꿔준다면 해당 열 1개와 바뀌는 행 2개를 바꿔주면 된다. (예를들어 아래 그림과 같이 초록색을 바꿔 준다면 영향을 받는 행과 열만 검사해주면된다.)

다다다음 생각

시간을 줄여주려고 바꾸는 x,y 값을 가지고 행을 바꿔줄 경우는 x,y,y+1로 열을 바꿔줄 경우는 x,x+1,y로 검사를 해주었다. 검사를 할 때 계속 전체 결과 값 result의 최대값을 찾아 갱신해 주었다.

▶ N이 크다면 실제로 성능에 영향을 많이 미칠지 모르겠지만 N이 작아 전체 탐색한 것과 많은 차이는 없었다.

▶ 오히려 코드만 길어진 느낌이다.

방안

1) N이 크지 않다면 전체 완전 탐색을 진행하는게 편하고 좋다는 생각이 든다.

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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113

package baekjoon.q3000;   import java.util.Scanner;   public class Q3085 {     static int n;     static int[][] arr;     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         n = sc.nextInt();         arr = new int[n][n];         for(int i=0;i<n;i++) {             String t = sc.next();             for(int j=0;j<n;j++)                 arr[i][j] = t.charAt(j);         }         // 결과 초기화         result = 0;                  // 다 바꿔보자         for(int i=0;i<n;i++) {             for(int j=0;j<n;j++)                 solve(i,j);         }         System.out.println(result);     }          static int result;     private static void solve(int x,int y) {         // 인근 칸만 바꿀 수 있으므로 자신의 오른쪽과 아래를 바꿔보자.                  // 1) 오른쪽 바꾸기         if(y<n-1) {             int t = arr[x][y];             arr[x][y] = arr[x][y+1];             arr[x][y+1] = t;             // 검사             check(x,y);             // 원상 복귀             arr[x][y+1] = arr[x][y];             arr[x][y] = t;         }         // 2) 아래 바꾸기         if(x<n-1) {             int t = arr[x][y];             arr[x][y] = arr[x+1][y];             arr[x+1][y] = t;             // 검사             check2(x,y);             // 원상 복귀             arr[x+1][y] = arr[x][y];             arr[x][y] = t;         }     }          private static void check2(int x,int y) {         int ty = arr[0][y], tx1=arr[x][0], tx2=arr[x+1][0];         int xCnt = 0, yCnt1=0, yCnt2=0;         for(int i=0;i<n;i++) {             // 세로를 바꿧을 때는 행 두개 열 하나 검사             if(tx1==arr[x][i]) {                 yCnt1++;             }else {                 tx1 = arr[x][i];                 yCnt1=1;             }             if(tx2==arr[x+1][i]) {                 yCnt2++;             }else {                 tx2 = arr[x+1][i];                 yCnt2=1;             }                          if(ty==arr[i][y]) {                 xCnt++;             }else {                 ty = arr[i][y];                 xCnt=1;             }             result=Math.max(result,Math.max(xCnt, Math.max(yCnt1,yCnt2)));         }     }          private static void check(int x,int y) {         int ty = arr[x][0], tx1=arr[0][y], tx2=arr[0][y+1];         int yCnt = 0, xCnt1=0, xCnt2=0;         for(int i=0;i<n;i++) {             // 가로를 바꿧을 때는 열 두개 행 하나 검사             if(tx1==arr[i][y]) {                 xCnt1++;             }else {                 tx1 = arr[i][y];                 xCnt1=1;             }                          if(tx2==arr[i][y+1]) {                 xCnt2++;             }else {                 tx2 = arr[i][y+1];                 xCnt2=1;             }                          if(ty==arr[x][i]) {                 yCnt++;             }else {                 ty = arr[x][i];                 yCnt=1;             }             result=Math.max(result,Math.max(yCnt, Math.max(xCnt1,xCnt2)));         }     } }