[브루트포스] 백준 - 사탕 게임

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

3085번: 사탕 게임

 

 

-문제해설

처음에 c, p, z, y 변수를 만들어서 연속되면 각 변수를 1씩 증가시키고 새로운 변수가 나오면 새로운 변수값을 1씩 증가시켰는데 이럴 필요가 없었다.

 

그냥 우측 혹은 아래측 문자가 현재 문자와 같으면 cnt 변수를 1씩증가시키고 max 값과 비교,

같지 않다면 cnt를 1로 초기화시키고 max값과 비교하는 식으로 풀면 되는 문제였다.

 

1. n을 입력받고 문자열 입력받은 뒤 .charAt()으로 문자로 나눠서 chu배열에 저장

 

2. 먼저 각 행에 대해서 우측사탕과 교환하고 최대값 구하는 과정을 반복한다.

 2-1. 우측사탕과 현재 사탕 자리바꿈

  char temp = chu[i][j];
  chu[i][j] = chu[i][j+1];
  chu[i][j+1] = temp;

 2-2. 사탕개수의 최대값 찾기( 행에 대한 최대값구하고 열에 대한 최대값 구한다. )

  check();

 2-3. 2-1에서 교환한 사탕 원위치 시키기

 

3. 다음으로 각 열에 대해서 아래측 사탕과 교환하고 최대값 구하는 과정 반복

 3-1. 아래측 사탕과 현재 사탕 자리바꿈

  char temp = chu[j][i];
  chu[j][i] = chu[j+1][i];
  chu[j+1][i] = temp;

 3-2. 사탕 개수의 최대값 찾기( 행에 대한 최대값구하고 열에 대한 최대값 구한다. )

  check();

 3-3 3-1에서 교환한 하탕 원위치 시키기

 

4. max값 출력

 

-자바

package bruteforce;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BJ3085 {
	public static char[][] chu;
	public static int n;
	public static int max = 0;
	
	//우측과 아래측 비교하면서 최대 사탕 개수 찾는 메서드
	public static void check() {
		//우측 먼저 체크
		for( int i=0; i<n; i++ ) {
			int cnt = 1;
			for( int j=0; j<n-1; j++ ) {
				//이전 값과 같으면 cnt 증가
				if( chu[i][j] == chu[i][j+1] ) cnt++;
				//이전 값과 다르면 cnt를 1로 초기화
				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( chu[j][i] == chu[j+1][i] ) cnt++;
				else cnt = 1;
				
				max = Math.max( max, cnt );
			}
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt( br.readLine() );
		chu = new char[n][n];
		
		String tmp = null;
		for( int i=0; i<n; i++ ) {
			tmp = br.readLine();
			for( int j=0; j<n; j++ ) chu[i][j] = tmp.charAt(j);
		}
		
		//가로로 인접한 두 사탕 교환하고 최대개수 찾은 뒤 다시 사탕 원위치시키기
		for( int i=0; i<n; i++ ) {
			for( int j=0; j<n-1; j++ ) {
				//가로로 인접한 두 사탕 교환
				char temp = chu[i][j];
				chu[i][j] = chu[i][j+1];
				chu[i][j+1] = temp;
				
				//오른쪽, 아래쪽 체크
				check();
				
				//위에서 교환했던 사탕 원위치
				temp = chu[i][j];
				chu[i][j] = chu[i][j+1];
				chu[i][j+1] = temp;
			}
		}
		
		//세로로 인접한 두 사탕 교환하고 최대개수 찾은 뒤 다시 사탕 원위치시키기
		for( int i=0; i<n; i++ ) {
			for( int j=0; j<n-1; j++ ) {
				//세로로 인접한 두 사탕 교환
				char temp = chu[j][i];
				chu[j][i] = chu[j+1][i];
				chu[j+1][i] = temp;
				
				//오른쪽, 아래쪽 체크
				check();
				
				//위에서 교환했던 사탕 원위치
				temp = chu[j][i];
				chu[j][i] = chu[j+1][i];
				chu[j+1][i] = temp;
			}
		}
		System.out.println( max );
		
	}
}

 

-파이썬

from sys import stdin
input = stdin.readline
n = int( input() )
arr = [ [0]*n for _ in range( n ) ]
for i in range( n ):
    s = input().rstrip()
    for j in range( n ):
        arr[i][j] = s[j]

def check( arr, n, ans ):
    for i in range( n ):
        cnt = 1
        for j in range( n-1 ):
            if arr[i][j] == arr[i][j+1]: cnt += 1
            else: cnt = 1
            ans = cnt if cnt > ans else ans
            
    for i in range( n ):
        cnt = 1
        for j in range( n-1 ):
            if arr[j][i] == arr[j+1][i]: cnt += 1
            else: cnt = 1
            ans = cnt if cnt > ans else ans
            
    return ans

ans = 0
#각 행에 대해서 자리바꾼 뒤 최대값 찾기
for i in range( n ):
    for j in range( n-1 ):
        tmp = arr[i][j]
        arr[i][j] = arr[i][j+1]
        arr[i][j+1] = tmp
        
        ans = check( arr, n, ans )
        
        tmp = arr[i][j]
        arr[i][j] = arr[i][j+1]
        arr[i][j+1] = tmp
        
#각 열에 대해서 자리바꾼 뒤 최대값 찾기
for i in range( n ):
    for j in range( n-1 ):
        tmp = arr[j][i]
        arr[j][i] = arr[j+1][i]
        arr[j+1][i] = tmp
        
        ans = check( arr, n, ans )
        
        tmp = arr[j][i]
        arr[j][i] = arr[j+1][i]
        arr[j+1][i] = tmp
print( ans )