[백준] 1018 (체스판 다시 칠하기)

#1 알고리즘

#1-1

 

#1-2

0-based indexing 및 1-based indexing에 대한 개념

 

#1-3

 

#1-4

 

#2 코드

#2-1 자바

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int yLength = sc.nextInt();
        int xLength = sc.nextInt();
        sc.nextLine(); // 입력 버퍼의 첫째 줄 비워내기
        
        // 자르기 전 원본 판떼기 2차원 배열로 만들기
        char[][] originalBoard = new char[yLength][xLength];
        for(int i = 0; i < yLength; i++) {
            String row = sc.nextLine();
            
            for(int j=0; j < xLength; j++) {
                originalBoard[i][j] = row.charAt(j);
            }
        }
        
        sc.close();
        
        int minCount = -1;
        
        // 체스판을 자르는 모든 경우의 수에 대해 calculateMinCountToMakeChessboard() 수행
        for(int i = 0; i < yLength - 7; i++) {          
            for(int j = 0; j < xLength - 7; j++) {
                int currentCount = calculateMinCountToMakeChessboard(originalBoard, i, j);  
                
                if(minCount == -1) {
                    minCount = currentCount;
                } else {
                    minCount = (minCount < currentCount) ? minCount : currentCount; 
                }
            }
        }
        
        System.out.println(Integer.toString(minCount));
    }
    
    public static int calculateMinCountToMakeChessboard(char[][] originalBoard, int yIndexBegin, int xIndexBegin) {
        /*
         * 맨 왼쪽이면서 맨 위쪽인 칸이
         * 'W'인 경우를 Case1,
         * 'B'인 경우를 Case2 로 명명한다
         */
        
        // Case 1 또는 2와 비교해서, 같은 칸을 몇 개 가지고 있는 지 Count
        int countMatchingForCase1 = 0; 
        int countMatchingForCase2 = 0;
              
        for(int i = yIndexBegin; i < yIndexBegin + 8; i++) {
            for(int j = xIndexBegin; j < xIndexBegin + 8; j++) {
                
                // 홀수 행 홀수 열
                if(i % 2 == 0 && j % 2 == 0) {
                    if(originalBoard[i][j] == 'W') {countMatchingForCase1++;} else {countMatchingForCase2++;}
                
                // 홀수 행 짝수 열
                } else if (i % 2 == 0 && j % 2 == 1) {
                    if (originalBoard[i][j] == 'B') {countMatchingForCase1++;} else {countMatchingForCase2++;}
                
                // 짝수 행 홀수 열
                } else if(i % 2 == 1 && j % 2 == 0) {
                    if (originalBoard[i][j] == 'B') {countMatchingForCase1++;} else {countMatchingForCase2++;}
                
                // 짝수 행 짝수 열
                } else { // (i % 2 == 1 && j % 2 == 1)
                    if (originalBoard[i][j] == 'W') {countMatchingForCase1++;} else {countMatchingForCase2++;}
                }
            }
        }
        
        // 완전한 Case 1 또는 2가 되기 위해서 칠해야 하는 횟수
        int countNeededForCase1 = 64 - countMatchingForCase1;
        int countNeededForCase2 = 64 - countMatchingForCase2;
        
        return (countNeededForCase1 < countNeededForCase2) ? countNeededForCase1 : countNeededForCase2;
    }
}

 

#2-2 코틀린

fun main() {
    val testCase = readLine()!!.trim()
    val testCaseValues = testCase.split(" ")
    val yLength = testCaseValues[0].toInt()
    val xLength = testCaseValues[1].toInt()
    
    /*
     * ''은 문자(Char)가 아니라 문자열(String)이다. Char 변수는 문자 하나를 저장하는 데이터 타입이기 때문이다.
     * 따라서 ''가 아니라 ' '와 같이 공백 문자를 표현해야 한다.
     * 자바 코드에서처럼 null로 초기화하지 않는 이유는, nullable Char 타입(Char?)을 쓰기 싫기 때문이다.
     */
    var originalBoard : Array<Array<Char>> = Array(yLength) {Array(xLength) {' '}}
    for(i : Int in 0..yLength - 1) {
        val row = readLine()!!
        
        for(j : Int in 0..xLength - 1) {
            originalBoard[i][j] = row.get(j)
        }
    }
    
    var minCount = -1
    
    for(i : Int in 0..yLength - 8) {
        for(j : Int in 0..xLength - 8) {
            val currentCount = calculateMinCountToMakeChessboard(originalBoard, i, j)
            
            if(minCount == -1) {
                minCount = currentCount
            } else {
                minCount = if(minCount < currentCount) {minCount} else {currentCount}
            }
        }
    }
    
    println(minCount.toString())
}

fun calculateMinCountToMakeChessboard(originalBoard : Array<Array <Char>>, yIndexBegin : Int, xIndexBegin : Int) : Int {
    var countMatchingForCase1 = 0
    var countMatchingForCase2 = 0
    
    for(i : Int in yIndexBegin..yIndexBegin + 7) {
        for(j : Int in xIndexBegin..xIndexBegin + 7) {
            // 홀수 행 홀수 열 (in 0-based indexing)
            if(i % 2 == 0 && j % 2 == 0) {
                if(originalBoard[i][j] == 'W') {countMatchingForCase1++} else {countMatchingForCase2++}
                
            // 홀수 행 짝수 열        
            } else if(i % 2 == 0 && j % 2 == 1) {
                if(originalBoard[i][j] == 'B') {countMatchingForCase1++} else {countMatchingForCase2++}
                
            // 짝수 행 홀수 열    
            } else if(i % 2 == 1 && j % 2 == 0) {
                if(originalBoard[i][j] == 'B') {countMatchingForCase1++} else {countMatchingForCase2++}
                
            // 짝수 행 짝수 열    
            } else { // i % 2 == 1 && j % 2 == 1
                if(originalBoard[i][j] == 'W') {countMatchingForCase1++} else {countMatchingForCase2++}
                                                        
            }
        }
    }
    
    val countNeededForCase1 = 64 - countMatchingForCase1
    val countNeededForCase2 = 64 - countMatchingForCase2
    
    return if(countNeededForCase1 < countNeededForCase2) {countNeededForCase1} else {countNeededForCase2}
}