[백준 알고리즘] 백준 3085번 사탕게임 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 3085번 사탕게임 자바(Java)

1) 문제번호 : 3085번

 

2) 문제 출처

www.acmicpc.net/problem/3085

3085번: 사탕 게임

 

2. 문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

 

 

3. 제약사항

- 

4. 입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

 

 

5. 출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

 

6. 풀이

- 이 문제에서는 한가지의 문제 해결 트릭을 찾으면 된다.

- 오른쪽 스왑을 하고 MAX값 찾고, 다시 값을 돌려놓는다. 이 패턴을 가지고 문제를 풀면 된다.

- 그래서, 스타트지점이 맨 오른쪽일 경우에는 아래로만 스왑하고, 스타트지점이 맨 아랫줄일 경우에는 오른쪽으로만 스왑한다.

- 그리고, 스타트지점이 N-1,N-1일 경우에는 그냥 스킵한다.

 

7. 소스 코드

import java.io.*;
import java.util.*;

public class Main {
	static int[][] map;
	static int N;
	static int MAX = Integer.MIN_VALUE;
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); // 보드의 크기

		map = new int[N][N];

		for (int i = 0; i < N; i++) {
			String s = sc.next();
			for (int j = 0; j < N; j++) {
				switch (s.substring(j, j + 1)) {
				case "C": // 빨
					map[i][j] = 1;
					break;
				case "P": // 파
					map[i][j] = 2;
					break;
				case "Z": // 초
					map[i][j] = 3;
					break;
				case "Y": // 노
					map[i][j] = 4;
					break;
				}
			}
		}
		

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				// i가 맨 밑이 아니고, j가 맨 오른쪽이라면 아래로만 스왑
				if (i != N - 1 & j == N - 1) {
					// 아래와 스왑
					int temp = map[i][j];
					map[i][j] = map[i+1][j];
					map[i+1][j] = temp;
					
					// MAX값 찾기
					MAX_SEARCH();
					
					//원래대로
					temp = map[i][j];
					map[i][j] = map[i+1][j];
					map[i+1][j] = temp;					
					continue;
				}
				
				//i가 맨 밑이고 j가 맨 오른쪽이 아니라면
				else if(i == N-1 & j!= N-1) {
					//오른쪽만 스왑
					int temp = map[i][j];
					map[i][j] = map[i][j+1];
					map[i][j+1] = temp;
					
					// MAX값 찾기
					MAX_SEARCH();
					
					//원래대로
					temp = map[i][j];
					map[i][j] = map[i][j+1];
					map[i][j+1] = temp;
					continue;
				}
				
				//맨 오른쪽 아래면
				else if(i==N-1 & j==N-1) break;
				
				// 오른쪽과 스왑
				int temp = map[i][j];
				map[i][j] = map[i][j+1];
				map[i][j+1] = temp;
				
				// MAX값 찾기
				MAX_SEARCH();
				
				//원래대로
				temp = map[i][j];
				map[i][j] = map[i][j+1];
				map[i][j+1] = temp;
				
				// 아래와 스왑
				temp = map[i][j];
				map[i][j] = map[i+1][j];
				map[i+1][j] = temp;
				
				// MAX값 찾기
				MAX_SEARCH();
				
				//원래대로
				temp = map[i][j];
				map[i][j] = map[i+1][j];
				map[i+1][j] = temp;
			}
		}
		System.out.println(MAX);
	}
	
	public static void MAX_SEARCH() {
		//오른쪽 검색
		int count = 1;
		
		out : for(int i=0;i<N;i++) {
			count = 1;
			for(int j=0;j<N-1;j++) {
				if(map[i][j]==map[i][j+1]) {
					count++;
					MAX = Math.max(MAX, count);
					if(MAX==N) break out;
					
				}
				else count = 1;
			}
		}
		
		count = 1;
		
		//아래 검색
		out : for(int i=0;i<N;i++) {
			count = 1;
			for(int j=0;j<N-1;j++) {
				if(map[j][i]==map[j+1][i]) {
					count++;
					MAX = Math.max(MAX, count);
					if(MAX==N) break out;
					
				}
				else count = 1;
			}
		}
	}
}

 

---