백준 3085번: 사탕 게임 [브루프토스][완전탐색][구현] - Java

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

3085번: 사탕 게임

봄보니게임이 뭔진 모르지만...

기준 좌표를 중심으로 위/아래/왼쪽/오른쪽 1칸씩 이동한 다른 사탕과 교환했을때 가장 긴 연속부분을 찾는 것.

 

728x90

//1. 모든 칸 다 돌기
//교환 전 긴연속부분 확인 --> 아무것도 교환 안했을때가.. 제일 긴 연속부분을 가지고 있을 수 있음(예제2참고)
//2. 인접한 사탕과 교환하기 (위/아래/오른쪽/왼쪽 4가지 case)

//다른 색깔 사탕인가?
//3. 교환
//4. 가장 긴 연속부분 찾기 (swap된 부분별로)
//5. 원복

package algorithm.boj;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj3085 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		
		System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//입력
		int N = Integer.parseInt(st.nextToken());
		
		char[][] board = new char[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			
			for (int j = 0; j < N; j++) {
				board[i][j] = str.charAt(j);
			}
		}
		
		int result = 0;
		//1. 모든 칸 다 돌기
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				
				//교환 전 긴연속부분 확인
				result = Math.max(result, findLong(board, i,j));
				
				//2. 인접한 사탕과 교환하기 (위/아래/오른쪽/왼쪽 4가지 case)
				//2-1.오른쪽
				if(j+1 < N) {
					//다른 색깔 사탕인가?
					if(board[i][j]!=board[i][j+1]) {
						//3. 교환
						swap(board, i,j,i,j+1);
						//4. 가장 긴 연속부분 찾기 (swap된 부분별로)
						result = Math.max(result, findLong(board, i,j));
						result = Math.max(result, findLong(board, i,j+1));
						//5. 원복
						swap(board, i,j+1,i,j);
					}					
				}
				//2-2.왼쪽
				if(j-1 > 0) {
					//다른 색깔 사탕인가?
					if(board[i][j]!=board[i][j-1]) {
						//교환
						swap(board, i,j,i,j-1);
						//가장 긴 연속부분 찾기 (swap된 부분별로)
						result = Math.max(result, findLong(board, i,j));
						result = Math.max(result, findLong(board, i,j-1));
						//원복
						swap(board, i,j-1,i,j);
					}					
				}
				//2-3.위쪽
				if(i-1 > 0) {
					//다른 색깔 사탕인가?
					if(board[i][j]!=board[i-1][j]) {
						//교환
						swap(board, i,j,i-1,j);
						//가장 긴 연속부분 찾기 (swap된 부분별로)
						result = Math.max(result, findLong(board, i,j));
						result = Math.max(result, findLong(board, i-1,j));
						//원복
						swap(board, i-1,j,i,j);
					}					
				}
				//2-3.아래쪽
				if(i+1 < N) {
					//다른 색깔 사탕인가?
					if(board[i][j]!=board[i+1][j]) {
						//교환
						swap(board, i,j,i+1,j);
						//가장 긴 연속부분 찾기 (swap된 부분별로)
						result = Math.max(result, findLong(board, i,j));
						result = Math.max(result, findLong(board, i+1,j));
						//원복
						swap(board, i+1,j,i,j);
					}					
				}
				
			}
		}
		System.out.println(result);
	}
	
	public static void swap(char[][] board, int bi, int bj, int ai, int aj) {
		char temp = board[bi][bj];
		board[bi][bj]=board[ai][aj];
		board[ai][aj]=temp;
	}
	
	public static int findLong(char[][] board, int i,int j) {
		int res = 1;
		
		// 행기준 가장 긴 연속부분 찾기
		char ch = board[i][0];
		int sum = 1;
		for (int y = 1; y < board.length; y++) {
			if(ch==board[i][y]) {
				sum++;
			} else {
				res = Math.max(res, sum);
				sum = 1;
				ch = board[i][y];
			}
		}
		res = Math.max(res, sum);
		
		// 열기준 가장 긴 연속부분 찾기
		ch = board[0][j];
		sum = 1;
		for (int x = 1; x < board.length; x++) {
			if(ch==board[x][j]) {
				sum++;
			} else {
				res = Math.max(res, sum);
				sum = 1;
				ch = board[x][j];
			}
		}
		res = Math.max(res, sum);
		return res;
	}

}

 

추가로 다른 사람 풀이를 봤을때.. 중복해서 swap하는 구간들이 생기니 그부분은 제거하는 꿀팁도 있었다.

(0.0) (0,1) (0,2) .... (N-1,N-1) 순으로 진행되기때문에 

(0.0)에서 이미 (0.1)과의 swap을 했으니 (0.1)에서는 (0.0)과 swap을 굳이 또 할 필요가 없다.

그러므로 위/아래/왼/오를 다 탐색하지말고... 아래/오른쪽만 봐도 무방하다..!