[Brute Force] 3085번 - 사탕게임

[백준] 3085번 - 사탕게임

📝 나의 풀이

모든 경우의 수를 다 계산해야 하기에 완전 탐색으로 풀어야 한다는 생각은 들었지만..
계속 어렵게 생각을 했다....!!! 그래서 안풀렸다.

문제에서 주어진 조건을 차근차근 다시 파악해보자.

1. 인접한(행, 열) 사탕의 위치를 서로 바꾼다.
2. 연속된 문자의 갯수가 가장 많은 것을 구한다.
3. 바꾼 사탕의 위치를 다시 돌려준다.

다음으로 단순하게 생각하자. 이렇게 3가지만 하면 된다!

• 행을 기준으로 오른쪽으로 탐색하면서 오른쪽 색상과 현재 색상을 바꿔주고 탐색하고 다시 돌려주기
• 열을 기준으로 아래쪽으로 탐색하면서 아래쪽 색상과 현재 색상을 바꿔주고 탐색하고 다시 돌려주기
• 행을 기준으로 왼쪽과 색을 변경해 줄 필요 없고 열을 기준으로 위쪽과 색을 변경해줄 필요 없다. 오른쪽 아래쪽을 바꿔가면서 변경했기 때문에 이미 바꿔줬던 색상이기 때문이다.

🔥 주의할 점

1. 행 기준, 열 기준으로 서로 다른 인접한 사탕을 탐색할 때 인덱스 위치를 잘 고려해서 풀어야한다.

2. 인접한 사탕을 탐색할 때
   행 기준으로 아래 방향, 열 기준으로 오른쪽 방향
   이렇게 두가지 방향만 고려해주면 된다.

👩🏻‍💻 최종 코드

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

public class Main {
	
	static char [][] map;
	static int N;
	static int maxCandy = 1;

	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 search() {
		
		// 행 기준으로 연속된 문자 탐색
		for(int i = 0; i < N; i++) {
			int count = 1;
			for(int j = 0; j < N - 1; j++) {
				if(map[i][j] == map[i][j+1]) {
					count++;
					maxCandy = Math.max(count, maxCandy);
				}
				else count = 1;
			}
		}
		
		// 열 기준으로 연속된 문자 탐색
		for(int i = 0; i < N; i++) {
			int count = 1;
			for(int j = 0; j < N - 1; j++) {
				if(map[j][i] == map[j+1][i]) {
					count++;
					maxCandy = Math.max(count, maxCandy);
				}
				else count = 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 input = br.readLine();
			for(int j = 0; j < N; j++) {
				map[i][j] = input.charAt(j);
			}
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N - 1; j++) {
				swap(i, j, i, j + 1);
				search();
				swap(i, j, i, j + 1);
			}
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N - 1; j++) {
				swap(j, i, j + 1, i);
				search();
				swap(j, i, j + 1, i);
			}
		}
		
		System.out.println(maxCandy);
		
	}

}

---

Reference

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