[BOJ][JAVA] 3085: 사탕 게임

 

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

3085번: 사탕 게임

 

import java.io.FileInputStream;
import java.util.Scanner;

class Main{
    public static void main(String[] args) throws Exception{
        System.setIn(new FileInputStream("res/input.txt"));

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        char[][] map = new char[n][n];
        for(int i=0; i<n; i++){
            char[] input = sc.nextLine().toCharArray();
            int idx = 0;
            for(char k: input){
                map[i][idx] = k;
            }
        }
        
        int ans = 0;
        // 서로 다른 두 개가 인접해 있는 경우를 찾아야 됨
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                // j+1 체크
                if(j == n-1){ // 마지막 열은 동일 행 다음 원소 비교 x
                    // i+1 체크
                    if(i == n-1){ // 마지막 행은 동일 열 다음 원소 비교 x
                        // 맨 마지막 위치이니 까 아무것도 안할것
                    }else{
                        if (map[i][j] != map[i+1][j]) {
                            swap(map, i, j, i+1, j);
                            int len = 1;
                            for(int a=1; a<n; a++){ // 열 고정
                                if(map[a-1][j] == map[a][j]){
                                    len++;
                                }else{
                                    len=1;
                                }
                                ans = Math.max(ans, len);
                            }
                            ans = Math.max(ans, len);
                            swap(map, i, j, i+1, j);
                        }
                    }
                }else{
                    if(i == n-1){ // 마지막 행은 동일 열 다음 원소 비교 x
                        if(map[i][j] != map[i][j+1]){
                            swap(map, i, j, i, j+1);
                            // 동일 행 최장길이 검색
                            int len = 1;
                            for(int a=1; a<n; a++){ // 행 고정
                                if(map[i][a-1] == map[i][a]){
                                    len++;
                                }else{
                                    len=1;
                                }
                                ans = Math.max(ans, len);
                            }
                            ans = Math.max(ans, len);
                            //원복
                            swap(map, i, j, i, j+1);
                        }
                    }else{// 이 경우가 일반적인 경우
                        if(map[i][j] != map[i][j+1]){
                            swap(map, i, j, i, j+1);
                            // 동일 행 최장길이 검색
                            int len = 1;
                            for(int a=1; a<n; a++){ // 행 고정
                                if(map[i][a-1] == map[i][a]){
                                    len++;
                                }else{
                                    len=1;
                                }
                                ans = Math.max(ans, len);
                            }
                            ans = Math.max(ans, len);
                            //원복
                            swap(map, i, j, i, j+1);
                        }
                        if (map[i][j] != map[i+1][j]) {
                            swap(map, i, j, i+1, j);
                            int len = 1;
                            for(int a=1; a<n; a++){ // 열 고정
                                if(map[a-1][j] == map[a][j]){
                                    len++;
                                }else{
                                    len=1;
                                }
                                ans = Math.max(ans, len);
                            }
                            ans = Math.max(ans, len);
                            swap(map, i, j, i+1, j);
                        }
                    }
                }
            }
        }

        System.out.println(ans);

        sc.close();
    }

    static void swap(char[][] map, int ai, int aj, int bi, int bj){
        char tmp = map[ai][aj];
        map[ai][aj] = map[bi][bj];
        map[bi][bj] = tmp;
    }
}

---

오답노트(푸는 동안 사고과정 및 개선점)

그냥 진행 방향을 r+1, c+1로만 제한해서 모든 경우를 탐색했다. 문제 유형 자체가 완전탐색이니 이렇게 해봤는데 답이 안나왔다.. 다시 풀어보자.

 

1/6일 오늘 안에 사탕게임 정복하자.

---

정답코드

import java.io.FileInputStream;
import java.util.Scanner;

class Main{
    public static void swapItem(char[][] map, int ia, int ja, int ib, int jb){
        char tmp = map[ia][ja];
        map[ia][ja] = map[ib][jb];
        map[ib][jb] = tmp;
    }

    public static int findMaxRow(char[][] map, int n){
        int tmpMax = 0;

        for(int i=0; i<n; i++){
            int len = 1;
            for(int j=1; j<n; j++){
                if(map[i][j-1] == map[i][j]){
                    len++;
                }else{
                    tmpMax = Math.max(tmpMax, len);
                    len = 1;
                }
            }
            tmpMax = Math.max(tmpMax, len);
        }
        return tmpMax;
    }

    public static int findMaxCol(char[][] map, int n){
        int tmpMax = 0;

        for(int i=0; i<n; i++){
            int len = 1;
            for(int j=1; j<n; j++){
                if(map[j-1][i] == map[j][i]){
                    len++;
                }else{
                    tmpMax = Math.max(tmpMax, len);
                    len = 1;
                }
            }
            tmpMax = Math.max(tmpMax, len);
        }
        return tmpMax;
    }

    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[][] map = new char[n][n];
        for(int i=0; i<n; i++){
            char[] input = sc.next().toCharArray();
            int idx = 0;
            for(char k: input){
                map[i][idx++] = k;
            }
        }

        int ans = 0;

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if (j+1 < n && map[i][j] != map[i][j+1]){ // 앞으로 교환
                    swapItem(map, i,j, i, j+1);
                    ans = Math.max(ans, Math.max(findMaxRow(map, n), findMaxCol(map,n)));
                    swapItem(map, i,j, i, j+1);
                }
                if (i+1 < n && map[i][j] != map[i+1][j]){ // 아래로 교환
                    swapItem(map, i,j, i+1, j);
                    ans = Math.max(ans, Math.max(findMaxRow(map, n), findMaxCol(map,n)));
                    swapItem(map, i,j, i+1, j);
                }
            }
        }

        System.out.println(ans);

        sc.close();
    }
}

 

정답코드를 입력하면서 함정에 빠졌던건 ans를 덮어쓰는 부분이다.

더 큰 값을 고를 때 ans의 이전 값도 신경쓰지않으면 행방향 교환할 때 열방향 교환 결과가 무시돼서 답이 제대로 안나온다. 완전 탐색이지만 배열 컨트롤에 가까웠던 문제 같다.

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^