13413번 오셀로 재배치

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

13413번: 오셀로 재배치

 

 

문제

 

 

소스코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str1 = "";
        String str2 = "";

        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            int diffBWNum = 0; //B,W 개수차이
            int diffPatternNum = 0; //다른 패턴의 개수
            int str1W = 0; //초기상태의 W 갯수
            int str2W = 0; //목표상태의 W 갯수

            str1 = br.readLine();
            str2 = br.readLine();
            for (int j = 0; j < n; j++) {
                if(str1.charAt(j) != str2.charAt(j)) diffPatternNum+=1;
                if(str1.charAt(j) == 'W') str1W+=1;
                if(str2.charAt(j) == 'W') str2W+=1;
            }
            diffBWNum = Math.abs(str1W - str2W);
            int result = (diffPatternNum - diffBWNum) / 2 + diffBWNum;
            sb.append(result + "\n");
        }
        bw.write(sb.toString()); bw.flush();
    }
}

 

 

해결방법

오셀로 재배치 작업

1. 배치된 말 중 임의의 2개의 말을 골라 서로의 위치를 바꾼다.
2. 말 1개를 들어 뒤집어 놓아 색상을 변경한다.

위의 두 가지 작업 중 하나로 재배치를 할 수있는데 최소 횟수로 재배치를 끝내야 하므로

작업1은 다른 패턴을 가지는 오셀로를 재배치하는데 유용하고,

작업2는 초기 상태의 오셀로와 목표 상태의 오셀로의 B,W 갯수가 다른 경우 재배치하는데 유용하다.

 

초기 상태의 오셀로와 목표 상태의 오셀로의 B,W 갯수가 다른 경우는 작업2로만 해결할 수 있으므로 일단 제쳐두고 작업1로 해결가능한 부분만 해결한 뒤에 작업2를 해주면 된다.

 

식은 "( 다른 패턴 개수 - B,W 개수차이 ) / 2 + B,W 개수차이" 가 된다.

 

 

훨씬 그리디적인 해결방법

소스코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str1 = "";
        String str2 = "";

        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            int cntW = 0; //W가 다른 갯수
            int cntB = 0; //B가 다른 갯수

            str1 = br.readLine();
            str2 = br.readLine();
            for (int j = 0; j < n; j++) {
                if(str1.charAt(j) != str2.charAt(j)) { //초기 상태와 목표 상태가 다를때
                    if(str1.charAt(j) == 'W') cntW+=1;
                    else cntB+=1;
                }
            }
            int result = cntW > cntB ? cntW : cntB;
            sb.append(result + "\n");
        }
        bw.write(sb.toString()); bw.flush();
    }
}

 

 

해결방법

초기 상태와 목표 상태를 비교해서 W가 다른 갯수, B가 다른 갯수만 구하면 답이 더 쉽게 나온다.
작업1로 할 수 있는 경우는 W가 다른 갯수와 B가 다른 갯수가 서로 증가하므로 둘 중 큰값이 작업1, 작업2로 만들 수 있는 최소 횟수가 된다.