알고리즘 실력이 떨어져서
다시 백준에서 문제를 풀고 있다.
다시 감 잡아야지!
문제
https://www.acmicpc.net/problem/1018
1018번: 체스판 다시 칠하기
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
www.acmicpc.net
설계
알고리즘 설계 [접근 방법] : 완전탐색
체스판을 8X8로 자른 후, 체스판의 색깔을 하나 하나 확인해야 하기 때문에 모든 경우의 수를 다 계산해야 한다.
만약 체스판이 예시 2번과 같이 10X13의 크기를 생각해보자!
(0, 0)에서 (7, 7)부터 체스판을 8X8로 자른 후 색깔이 맞는지 확인해본다.
그 후 (0, 1)부터 (7, 8) 로 자른 후 다시 색깔을 비교한다. 그런 식으로 마지막인 (2, 5)에서 (10, 13)까지
색깔을 비교 한 후 색깔을 안바꾸는 경우가 가장 작았을 때의 개수를 출력하면 된다.
풀이 과정
1.
h와 w를 입력받은 후, map이라는 2차원 배열 크기에 색깔을 입력받는다.
2.
정답 변수인 min을 최대값으로 초기화한다.
(0, 0)부터 isMin 메서드를 적용한다.
3.
체스판이 B로 시작할 때와 W로 시작할 때를 비교하기 위해 bw만큼 반복한다.
isMin메서드에서 hn이 시작하는 행의 인덱스이고, wn가 열의 인덱스이다.
그렇기에 반복문을 hn+8, wn+8로 반복해 8X8크기만 색깔을 비교한다.
4.
체스판의 색깔과 배열 bw값을 비교해야하는데, t가 0일 때는 체스판이 B로 시작하는 경우이고 t가 1일 때는 W로 시작하는 경우다.
point는 배열bw의 값을 번갈아가면서 B, W, B, W로 해야 하기 때문에 ++를 해야하고, 배열의 인덱스를 넘지 않기 위해 %2를 해줬다.
5.
여기서 한 줄이 W로 끝나면 다음 줄 첫 번째 칸도 W로 시작해야하기 때문에, point++를 해줬다.
6.
static 변수인 min과 이번에 개수를 센 count와 비교하여 count가 더 작다면, min을 변경한다.
코드
import java.util.Scanner;
public class Test_1018_체스판다시칠하기 {
static char[][] map;
static int min;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int h = sc.nextInt();
int w = sc.nextInt();
map = new char[h][w];
for(int i=0; i<h; i++) {
map[i] = sc.next().toCharArray();
}
min = Integer.MAX_VALUE;
//0,0부터 시작
for(int i=0; i+8<=h; i++){
for(int j=0; j+8<=w ; j++){
min = isMin(i, j);
}
}
//출력
System.out.println(min);
}
public static int isMin(int hn, int wn) {
char[] bw = {'B', 'W'};
int point=0;
for(int t=0; t<bw.length; t++) {
int count = 0;
for(int i=hn; i<hn+8; i++) {
for(int j=wn; j<wn+8; j++) {
if(map[i][j]!=bw[(t+point++)%2]) count++;
}
point++; //B 아랫줄에는 W여야하기 때문에 point 한 번 건너뛰기
}
min = Math.min(min, count);
}
return min;
}
}
(❁´◡`❁)
끝!
'[자료구조] 알고리즘' 카테고리의 다른 글
[백준] 17219번 비밀번호 찾기 (Map, JAVA) (0) | 2024.01.10 |
---|---|
[백준] 1003번 피보나치함수 (DP_JAVA) (1) | 2024.01.09 |
[프로그래머스] 할인 행사(슬라이딩 윈도우_JAVA) (2) | 2024.01.03 |
[프로그래머스] 구명보트(투포인터_JAVA) (1) | 2023.11.29 |
[프로그래머스] 점프와 순간이동 (DP_JAVA) (0) | 2023.11.23 |