1018번: 체스판 다시 칠하기

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

www.acmicpc.net

실버5문제인데 풀지 못했다. 크게 어렵지 않다고 생각했는데 테케조차 통과하지 못했고 어떤 방법이 문제였는지 피드백을 해보겠다.

접근 아이디어

첫 접근은 간단했다. 4중for문으로 맨왼쪽위에 값을 기본값으로 넣고 다음 값이 맨 윗값과 같으면 count+1을 하고 다르면 맨 윗값에 넣은 값을 바꿔주는 방식으로 설계했다.

BWBWBW

WBWBWB

처럼 2번째 라인의 경우 전 라인의 값과 달라야 하므로 2번째줄 첫 번째 값은 그 전줄에 있는 값과 같으면 count+1을 했다. 이유는 잘 모르겠지만 테스트케이스조차 통과하지 못했다.

두 번째는 홀짝으로 접근했다. 홀수 자리인 경우와 짝수 자리를 계산해서 짝수면 첫 값과 같고 다르면 count+1을 해줬다. 하지만 이 방법도 틀렸다.

package backjon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static char[][] arr;
	static int max;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new char[N][];
		for (int i = 0; i < N; i++) {
			arr[i] = br.readLine().toCharArray();
		}
		max = Integer.MAX_VALUE;
		// 8개씩 골라서 최소값 비교. 4종for문필요함
		for (int q = 0; q <= N - 8; q++) {
			for (int w = 0; w <= M - 8; w++) {
				// 같은 색인지 비교하기 위해서 변수 선언
				char board = arr[q][w];
				int count = 0;
				for (int i = q; i < q + 8; i++) {
					for (int j = w; j < w + 8; j++) {
						if (i == q && j == w)
							continue;
						// i j가 홀수면 board랑 다름
						if (i % 2 == 0) {
							if (j % 2 == 0) {
								if (arr[i][j] != board)
									count++;
							} else {
								if (arr[i][j] == board)
									count++;
							}
						} else {
							if (j % 2 != 0) {
								if (arr[i][j] != board)
									count++;
							} else {
								if (arr[i][j] == board)
									count++;
							}
						}
					}
				}
				max = Math.min(max, count);
			}
		}

		System.out.println(max);
	}
}

결국 다 푼사람에게 설명을 들었다. 맨 왼쪽 위 값을 고정하는게 아니라 B일때와 W일 때 둘다 비교해서 값을 찾아야했다. 기존 코드를 활용해서 위 방식대로 설계했다.

public class Main {

	static int N, M;
	static char[][] arr;
	static int max;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new char[N][];
		for (int i = 0; i < N; i++) {
			arr[i] = br.readLine().toCharArray();
		}
		max = Integer.MAX_VALUE;
		// 8개씩 골라서 최소값 비교. 4종for문필요함
		for (int q = 0; q <= N - 8; q++) {
			for (int w = 0; w <= M - 8; w++) {
				
				int count = chess(q,w,'B','B');
				max = Math.min(max, count);
				count = chess(q,w,'W','W');
				max = Math.min(max, count);
			}
		}

		System.out.println(max);
	}
	
	static int chess(int q, int w, char board, char start) {
		int count = 0;;
		for (int i = q; i < q + 8; i++) {
			for (int j = w; j < w + 8; j++) {
				if (i == q && j == w)
					continue;
				//i가 첫번째 줄이라면
				if(i == q) {
					if(arr[i][j] == board) count++;
					board = board == 'B' ? 'W' : 'B';
				//두번째 줄 첫번째 값은 윗값과 비교
				}else {
					if(j==w) {
						if(arr[i][j] == start) count++;
						start = start == 'B' ? 'W' : 'B';
					}else {
						if(arr[i][j] == board) count++;
						board = board == 'B' ? 'W' : 'B';
					}
				}
			}
		}
		return count;
	}
	
}

이 코드도 테스트케이스 하나를 통과하지 못했다. 왜 틀린지 한참을 디버깅해보고나서야 답을 찾았다.

첫 값은 continue로 넘어가는데 첫 값이 틀린 경우 count되지 않아서 발생하는 문제였다. if문으로 첫 값이 다를 때 count값을 1 증가시키는 걸로 해결했다. 사실 if문을 추가하지 않고 continue문을 삭제해도 된다.

package backjon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static char[][] arr;
	static int max;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new char[N][];
		for (int i = 0; i < N; i++) {
			arr[i] = br.readLine().toCharArray();
		}
		max = Integer.MAX_VALUE;
		// 8개씩 골라서 최소값 비교. 4종for문필요함
		for (int q = 0; q <= N - 8; q++) {
			for (int w = 0; w <= M - 8; w++) {
				
				int count = chess(q,w,'B','B');
				max = Math.min(max, count);
				count = chess(q,w,'W','W');
				max = Math.min(max, count);
			}
		}

		System.out.println(max);
	}
	
	static int chess(int q, int w, char board, char start) {
		int count = 0;
		if(board != arr[q][w]) count++;
		for (int i = q; i < q + 8; i++) {
			for (int j = w; j < w + 8; j++) {
				if (i == q && j == w)
					continue;
				//i가 첫번째 줄이라면
				if(i == q) {
					if(arr[i][j] == board) count++;
					board = board == 'B' ? 'W' : 'B';
				//두번째 줄 첫번째 값은 윗값과 비교
				}else {
					if(j==w) {
						if(arr[i][j] == start) count++;
						start = start == 'B' ? 'W' : 'B';
					}else {
						if(arr[i][j] == board) count++;
						board = board == 'B' ? 'W' : 'B';
					}
				}
			}
		}
		return count;
	}
	
}

잘 한 부분

접근도 잘못했고 답도 찾지 못했다.

부족한 부분

문제를 제대로 이해하지 못했다. 아니 이해했다고 착각했다. 문제를 분석하듯이 읽어야 하는데 물 흐르듯이 두 세번 읽고 이해했다고 착각했다.

디버깅을 귀찮아했다. 답변을 들은 후 디버깅에 좀 더 집중하면 문제를 풀 수 있었는데 아쉽다.

정리하자면 한 번 생각한 방법에 매몰돼서 새로운 방법을 생각하지 못한게 이 문제를 풀지 못한 이유인거 같다. 4중for문 설계 후 맨 왼쪽값을 고정 시킨채 두 번의 풀이가 모두 오답으로 나왔다면 내가 문제를 잘못 이해했는지 체크했어야 했는데 실버5에 정답률도 높으니 그런 생각을 하지 않고 코드에만 집중한게 원인인 것 같다.

문제를 잘 이해하는 것도 엄청 중요한데 쉽지 않다.

저작자표시

'알고리즘' 카테고리의 다른 글

백준 1436 자바 (0)	2022.03.07
백준 2470 자바 (0)	2022.03.07
백준 2231 자바 (0)	2022.03.05
백준 2636 치즈 자바 (0)	2022.03.05
백준 3085 파이썬 (0)	2021.11.23

백준 1018 체스판 다시 칠하기

접근 아이디어

잘 한 부분

부족한 부분

'알고리즘' 카테고리의 다른 글

티스토리툴바