(JAVA) 백준 3085번 : 사탕 게임

https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

첫번째 시도 (실패)

- n의 크기가 그리 크지 않기에 단순하게 구해보았다.

- 가로로 교환할 때, 세로로 교환할 때로 크게 나누고 원래의 값과 바꾸는 대상을 div로 

- 중복은 많지만 나중에 없앨 수 있을것 같다.

import java.io.InputStreamReader;
import java.io.BufferedReader;
 
public class Main {
    static char[][] G;
    static int n;
    static int[][] div = {{0,0},{-1,0},{1,0}};//lDiv시 ij 바꾸기
    static boolean Valid(int x, int y) {
        if (x<0||x>=n) return false;
        if (y<0||y>=n) return false;
        return true;
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        G = new char[n][n];
        for (int i=0;i<n;i++) {
            String s = br.readLine().strip();
            for (int j=0;j<n;j++) 
                G[i][j] = s.charAt(j);
        }
        int mx=-1;
        for (int i=0;i<n;i++) { //w
            
            for (int j=0;j<n;j++) {
                
                for (int k=0;k<3;k++) {
                    int x = i+div[k][0],y = j+div[k][1];
                    if (Valid(x,y)==false) continue;
                    char pp ='0';
                    int a=0;
                    for (int p=0;p<n;p++) {
                        char t = G[i][p];
                        if (j==p) t = G[x][y];
                        if (t!=pp) {
                            mx = Math.max(mx, a);
                            pp=t; a=1;
                        }
                        else a+=1;
                    }
                    mx = Math.max(mx, a);
                }
            }
        }
        
        for (int j=0;j<n;j++) { //l
            
            for (int i=0;i<n;i++) {
                
                for (int k=0;k<3;k++) {
                    int x = i+div[k][1],y = j+div[k][0];
                    if (Valid(x,y)==false) continue;
                    char pp ='0';
                    int a=0;
                    for (int p=0;p<n;p++) {
                        char t = G[p][j];
                        if (i==p) t = G[x][y];
                        if (t!=pp) {
                            mx = Math.max(mx, a);
                            pp=t; a=1;
                        }
                        else a+=1;
                    }
                    mx = Math.max(mx, a);
                }
            }
        }
        System.out.println(mx);
    }
 
}
 

 - 첫 시도에서는 2쌍의 사탕이 바뀔 때 변하는 것이 j와 j+div[x][1]이라고 생각하고 진행했다. 그러나 사탕을 바꿨을때 영향을 받는 행 또는 열을 고려해야하기에 두번째 시도에서는 그것을 고쳐보았다.

 

두번째 시도 (성공)

- 첫번째 시도에서 고려하지 못했던 '바뀌는 사탕쌍이 모두 포함된 행 또는 열'을 고려하여 보았다. 

import java.io.InputStreamReader;
import java.io.BufferedReader;
 
public class Main {
    static char[][] G;
    static int n;
    static int[][] div = {{0,0},{-1,0},{1,0}};
    static boolean Valid(int x, int y) {
        if (x<0||x>=n) return false;
        if (y<0||y>=n) return false;
        return true;
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        G = new char[n][n];
        for (int i=0;i<n;i++) {
            String s = br.readLine().strip();
            for (int j=0;j<n;j++) 
                G[i][j] = s.charAt(j);
        }
        int mx=-1;
        for (int i=0;i<n;i++) { 
            
            for (int j=0;j<n;j++) {
                
                for (int k=0;k<3;k++) {
                    int x = i+div[k][0],y = j+div[k][1];
                    if (Valid(x,y)==false) continue;
                    char pp ='0';
                    int a=0;
                    for (int p=0;p<n;p++) {
                        char t = G[i][p];
                        if (j==p) t = G[x][y];
                        if (t!=pp) {
                            mx = Math.max(mx, a);
                            pp=t; a=1;
                        }
                        else a+=1;
                    }
                    mx = Math.max(mx, a);
                    pp ='0';
                    a=0;
                    for (int p=0;p<n;p++) {
                        char t = G[p][j];
                        if (p==x) t = G[i][j];
                        else if (p==i) t = G[x][y]; 
                        if (t!=pp) {
                            mx = Math.max(mx, a);
                            pp=t; a=1;
                        }
                        else a+=1;
                    }
                    mx = Math.max(mx, a);
                    
                }
            }
        }
        
        for (int j=0;j<n;j++) { 
            
            for (int i=0;i<n;i++) {
                
                for (int k=0;k<3;k++) {
                    int x = i+div[k][1],y = j+div[k][0];
                    if (Valid(x,y)==false) continue;
                    char pp ='0';
                    int a=0;
                    for (int p=0;p<n;p++) {
                        char t = G[p][j];
                        if (i==p) t = G[x][y];
                        if (t!=pp) {
                            mx = Math.max(mx, a);
                            pp=t; a=1;
                        }
                        else a+=1;
                    }
                    mx = Math.max(mx, a);
                    pp ='0';
                    a=0;
                    for (int p=0;p<n;p++) {
                        char t = G[i][p];
                        if (p==y) t = G[i][j];
                        else if (p==j) t = G[i][y]; 
                        if (t!=pp) {
                            mx = Math.max(mx, a);
                            pp=t; a=1;
                        }
                        else a+=1;
                    }
                    mx = Math.max(mx, a);
                }
            }
        }
        System.out.println(mx);
    }
 
}
 

 

- 이 경우 성공했다. 

 

 

효율화를 위한 세부사항

- int[][] div의 경우 [x][0]은 바뀌는 것 없이 0으로 되어있기에 일차원 배열로 수정하는것이 불필요한 부분을 줄일 수 있을 것 같다.

- 바뀌는 2쌍의 사탕이 있다면 그것을 기준으로 j와 j+1,그리고 i에 대해 변한 이후의 최대연속 길이를 찾는다. 효율화를 위해  바뀌는 2쌍의 가짓수만 가지고 다음의 3가지 경우에 대한 길이를 찾는다. (위의 소스코드에서는 겹치는 부분이 존재한다.) 

 

후기

- 실버 2의 난이도로 쉬운편이지만 고려하지 못한 부분이 많아 생각보다 시간을 쓴 문제였다. 

- 어떠한 작업이 일어났을때 어느 범위까지 영향을 미치는지를 확인하면서 문제를 풀자..