[백준/JAVA] 3085번: 사탕 게임

🔺 문제

3085번: 사탕 게임

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static char[][] board;
    static int N;
    static int max = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        board = new char[N][N];
        
        // N x N 사탕 입력 받기
        for(int i = 0 ; i < N ; i++) {
            String str = br.readLine();
            for(int j = 0 ; j < board[i].length ; j++) {
                board[i][j] = str.charAt(j);
            }
        }
        
        // "행" 기준 오른쪽 색과 변경
        for(int i = 0 ; i < N ; i++) {          // 행
            for(int j = 0 ; j < N - 1 ; j++) {  // 열
                // 1) 가로로 인접한 두 문자 교환
                char tmp = board[i][j];
                board[i][j] = board[i][j + 1];
                board[i][j + 1] = tmp;
                
                // 2) 최대 사탕 갯수 찾기
               search();
                
                // 3) 교환한 문자 원 위치 복구
                tmp = board[i][j];
                board[i][j] = board[i][j + 1];
                board[i][j + 1] = tmp;
            }
        }
        
        // "열" 기준 아래쪽 색과 변경
        for(int i = 0 ; i < N ; i++) {          // 열
            for(int j = 0 ; j < N - 1 ; j++) {  // 행
               // 1) 가로로 인접한 두 문자 교환
                char tmp = board[j][i];
                board[j][i] = board[j + 1][i];
                board[j + 1][i] = tmp;
                
               // 2) 최대 사탕 갯수 찾기
               search();
                
               // 3) 교환한 문자 원 위치 복구
                tmp = board[j][i];
                board[j][i] = board[j + 1][i];
                board[j + 1][i] = tmp;            
            }
        }
        
        System.out.println(max);
        br.close();
    }
    
    // 가로세로 비교하면서 먹을 수 있는 최대 사탕 갯수 찾는 메소드
    public static void search() {
        // 가로에서 긴 수열 탐색
        for(int i = 0 ; i < N ; i++) {
            int cnt = 1;
            for(int j = 0 ; j < N - 1 ; j++) {
                if(board[i][j] == board[i][j + 1])    // 이전 사탕과 동일한 경우
                    cnt++;
                else    // 다르면 새로 먹기
                    cnt = 1;
                    
                max = Math.max(max, cnt);
            }
        }
        
        // 세로에서 긴 수열 탐색
        for(int i = 0 ; i < N ; i++) {
            int cnt = 1;
            for(int j = 0 ; j < N - 1 ; j++) {
                if(board[j][i] == board[j + 1][i])
                    cnt++;
                else
                    cnt = 1;
                    
                max = Math.max(max, cnt);
            }
        }  
    }
}
 

✅ 해결 아이디어
✔ 브루트포스 / 완전 탐색
- 조건에 따라 그대로

 

💥 유의사항

• swap 함수로 값을 교환한다고 해도, 실제로 값 교환은 안 된다고 한다.

 

---

🔺 다른 풀이들

- 최고의 설명 (복습용)

[자바]백준 3085번 사탕게임[브루트포스][엄탱]

 

---

💬 느낀 점

조건에 따라 그대로..가 말이 쉽지

나는 아직 어려운 것 같다...

 

배열 따라 이동.. 이런거 아직도 모르겠움,,

복습해서 쉽게 풀어보리겠어

 

 

1회독	2회독	3회독	4회독	5회독
V	240114	240627

 

 

(+2회독 240114 - 14376KB, 196ms)

다 맞게 작성했는데 "열"을 기준으로 swap하고 최대 사탕 갯수 구할 때

arr[j][i], arr[j + 1][i]로 작성해야 했는데 arr[i][j], arr[i][j + 1]로 작성해서 틀렸다,,,,,,

 

담엔 열도 꼭 맞추기,,

 

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static char[][] arr;
 
    static int max = 1;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = Integer.parseInt(br.readLine());
        arr = new char[N][N];
 
        for(int i = 0 ; i < N ; i++) {
            String s = br.readLine();
            for(int j = 0 ; j < N ; j++) {
                arr[i][j] = s.charAt(j);
            }
        }
 
        // 좌우 두 점 골라 확인하기
        for(int i = 0 ; i < N ; i++) {          // 행
            for(int j = 0 ; j < N - 1 ; j++) {  // 열
                // swap하기
                char c = arr[i][j];
                arr[i][j] = arr[i][j + 1];
                arr[i][j + 1] = c;
 
                // 최대 사탕 갯수 찾기
                search();
 
                // 원상복구
                c = arr[i][j];
                arr[i][j] = arr[i][j + 1];
                arr[i][j + 1] = c;
            }
        }
 
 
        // 위아래 두 점 골라 확인하기
        for(int i = 0 ; i < N ; i++) {          // 열
            for(int j = 0 ; j < N - 1 ; j++) {  // 행
                // swap하기
                char c = arr[j][i];
                arr[j][i] = arr[j + 1][i];
                arr[j + 1][i] = c;
 
                // 최대 사탕 갯수 찾기
                search();
 
                // 원상복구
                c = arr[j][i];
                arr[j][i] = arr[j + 1][i];
                arr[j + 1][i] = c;
            }
        }
 
        System.out.println(max);
    }
 
    private static void search() {
        // 가장 긴 연속 부분 "행" 찾기
        for(int i = 0 ; i < N ; i++) {          // 행
            int cnt = 1;
 
            for(int j = 0 ; j < N - 1 ; j++) {  // 열
                if(arr[i][j] == arr[i][j + 1]) {
                    cnt++;
                }
                else {
                    cnt = 1;
                }
 
                max = Math.max(max, cnt);
            }
        }
 
        // 가장 긴 연속 부분 "열" 찾기
        for(int i = 0 ; i < N ; i++) {          // 열
            int cnt = 1;
 
            for(int j = 0 ; j < N - 1 ; j++) {  // 행
                if(arr[j][i] == arr[j + 1][i]) {
                    cnt++;
                }
                else {
                    cnt = 1;
                }
 
                max = Math.max(max, cnt);
            }
        }
    }
}
 

 

 

 

(+ 3회독 240627 - 14392KB, 188ms)

사탕 색이 다른 인접한 두 칸을 swap하는 함수를 따로 빼서 생성했다.

거의 다 맞게 작성했고, 이번에도 놓친 부분은 열 부분 구할 때 처리,,,

 

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static char[][] map;
    static int max = 1;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        
        for(int i = 0 ; i < N ; i++) {
            String s = br.readLine();
            for(int j = 0 ; j < N ; j++) {
                map[i][j] = s.charAt(j);
            }
        }
        
        // 가로 2칸 고르기
        for(int i = 0 ; i < N ; i++) {  // 행
            for(int j = 0 ; j < N-1 ; j++) {    // 열
                if(map[i][j] != map[i][j+1]) {
                    swap(i, j, i, j+1);
                    calc();
                    swap(i, j, i, j+1);
                }
            }
        }
        
        // 세로 2칸 고르기
        for(int i = 0 ; i < N ; i++) {  // 열
            for(int j = 0 ; j < N-1 ; j++) {    // 행
                if(map[j][i] != map[j+1][i]) {
                    swap(j, i, j+1, i);
                    calc();
                    swap(j, i, j+1, i);
                }
            }
        }
        
        System.out.println(max);
    }
    
    // (x1,y1)과 (x2,y2) 자리의 원소 바꾸는 메소드
    private static void swap(int x1, int y1, int x2 ,int y2) {
        char tmp = map[x1][y1];
        map[x1][y1] = map[x2][y2];
        map[x2][y2] = tmp;
    }
    
    private static void calc() {
        // 행에서 가장 긴 연속 부분 찾기
        for(int i = 0 ; i < N ; i++) {  // 행
            int cnt = 1;
            
            for(int j = 0 ; j < N-1 ; j++) {    // 열
                if(map[i][j] == map[i][j+1]) {
                    cnt++;
                    max = Math.max(max, cnt);
                }
                else {
                    cnt = 1;
                }
            }
        }
        
        // 열에서 가장 긴 연속 부분 찾기
        for(int i = 0 ; i < N ; i++) {  // 열
            int cnt = 1;
            
            for(int j = 0 ; j < N-1 ; j++) {    // 행
                if(map[j][i] == map[j+1][i]) {
                    cnt++;
                    max = Math.max(max, cnt);
                }
                else {
                    cnt = 1;
                }
            }
        }
    }
}

안녕

 

---

(참고)

[백준] 3085번: 사탕 게임(완전 탐색)

백준 3085번 사탕 게임 자바 풀이