백준 12886번: 돌 그룹(Python/Java)

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

12886번: 돌 그룹

 

 

 

접근

---

이 문제가 너비 우선 탐색이라는 것을 생각만 해낸다면 어렵지 않게 풀 수 있는 쉬운 문제. 하지만 이를 구현해내는 부분에서 재미있는 아이디어가 두 가지 정도 있어 그 부분을 짚고 넘어가야겠다 생각했다.

 

우선 첫 번째로 세 개의 그룹에서 두 개의 그룹을 골라 확인하는 방법이었다. 물론 첫 번째와 두 번째, 첫 번째와 세 번째, 두 번째와 세 번째, 이렇게 세 개의 그룹을 각각 골라 직접 비교할 수도 있다. 하지만 그렇게 직접 박아 넣는 방법은 딱 보기에도 좋다는 생각은... 안 든다. 그래서 최대한 하드 코딩을 줄이고 짧게 비교하는 방법을 생각해봤고, 나온 결론은 for문을 돌려서 3으로 나눈 나머지를 인덱스로 두는 것이다. 예를 들어 살펴보자

for i in range(3):
    print(i%3, (i+1)%3)

위 코드와 같이 0~2 범위 for문을 돌리고 해당 인덱스에서 3을 나눈 나머지, 그리고 해당 인덱스의 1을 더한 값에서 3을 나눈 나머지를 구하면 각각 [0, 1], [1, 2], [2, 0]이 나온다. 즉, 앞서 말한 3개를 각각 비교하는 경우의 수를 모두 구할 수 있다. 이제 그룹들을 배열을 만들어 순차대로 넣고, 위 방법을 통해 배열의 인덱스를 구한 뒤 비교하면 모든 그룹을 비교할 수 있다.

 

다음으로 살펴볼 것은 방문 여부 구현이다. 처음에는 단순히 첫 번째 그룹, 두 번째 그룹, 세 번째 그룹 각각 될 수 있는 모든 개수를 인덱스로 하여 3차원 배열을 만들고, Queue에 각각 될 수 있는 모든 개수 별로 넣고 돌렸다. 물론 메모리 초과. 이 배열과 연산을 어떻게 더 줄일 수 있을까 생각하다가 나온 방법이 2차원 배열로 만드는 것이었다.

 

문제에서 다른 조건이 없으니 세 개의 돌 그룹 내의 총 돌 개수는 변함이 없다. 그렇기 때문에 이때 가장 많은 돌의 개수와 가장 적은 돌의 개수를 생각하면 중간 값의 돌 개수는 굳이 셀 필요가 없다. 가장 큰 돌의 개수와 가장 적은 돌의 개수가 있으면 나머지 하나는 자동으로 정해지기 때문이다. 즉, 방문 여부는 3차원이 아니라 2차원만 하더라도 충분하다.

 

또, 방문 여부를 체크할 때 중복되는 방문을 빼줘야 한다. 예를 들어 2개, 5개, 10개라는 세 돌 그룹이 있다고 해보자. 이때, 방문 여부는 2X10에 체크될 것이다. 그런데 여러 번 연산을 반복해보니 10개, 5개, 2개가 되었다고 해보자. 이때 우리는 10X2에 체크해야 할까? 아니다. 이 경우에는 연산을 돌리지 않아야 한다. 2개, 5개, 10개 조합이든 10개, 5개 2개 조합이든 결국 연산되는 결과는 같을 것이기 때문이다. 이를 다른 것으로 판단하고 계속 연산하면 마치 2+10와 10+2를 다른 연산으로 생각하고 반복 계산하는 꼴이 될 것이다. 즉, 그게 세 그룹 중 어떤 그룹이 되었든 가장 큰 값과 가장 작은 값을 비교해서 해당 인덱스에 방문한 적 있다면 중복 체크를 해주도록 하자.

 

 

 

풀이

---

Python

from collections import deque

firstNum, secondNum, thirdNum = map(int, input().split())
allNum = (firstNum + secondNum + thirdNum)
visitList = [[False for i in range(allNum+1)] for i in range(allNum+1)]

bfsDeque = deque()
bfsDeque.append([firstNum, secondNum, thirdNum])

result = 0
while bfsDeque:
    thisDeque = bfsDeque.popleft()

    if thisDeque[0] == thisDeque[1] == thisDeque[2]:
        result = 1
        break

    for i in range(3):
        subDeque = [thisDeque[0], thisDeque[1], thisDeque[2]]
        if thisDeque[i%3] != thisDeque[(i+1)%3]:
            if thisDeque[i%3] > thisDeque[(i+1)%3]:
                subDeque[i%3] -= thisDeque[(i+1)%3]
                subDeque[(i+1)%3] += thisDeque[(i+1)%3]
            else:
                subDeque[i%3] += thisDeque[i%3]
                subDeque[(i+1)%3] -= thisDeque[i%3]

            maxNum = max(subDeque)
            minNum = min(subDeque)

            if not visitList[maxNum][minNum]:
                visitList[maxNum][minNum] = True
                bfsDeque.append([subDeque[0], subDeque[1], subDeque[2]])

print(result)

 

Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        String[] firstLine = (scan.nextLine()).split(" ");
        int firstNum = Integer.parseInt(firstLine[0]);
        int secondNum = Integer.parseInt(firstLine[1]);
        int thirdNum = Integer.parseInt(firstLine[2]);

        int allNum = (firstNum + secondNum + thirdNum);
        boolean[][] visitList = new boolean[allNum+1][allNum+1];

        Queue<int[]> bfsQueue = new LinkedList<>();
        bfsQueue.add(new int[] {firstNum, secondNum, thirdNum});

        int result = 0;
        while(!bfsQueue.isEmpty()){
            int[] thisQueue = bfsQueue.poll();

            if(thisQueue[0] == thisQueue[1] && thisQueue[0] == thisQueue[2] && thisQueue[1] == thisQueue[2]){
                result = 1;
                break;
            }

            for(int i = 0 ; i < 3 ; i++){
                int[] subQueue = {thisQueue[0], thisQueue[1], thisQueue[2]};
                if(thisQueue[i%3] != thisQueue[(i+1)%3]){
                    if(thisQueue[i%3] > thisQueue[(i+1)%3]){
                        subQueue[i%3] -= thisQueue[(i+1)%3];
                        subQueue[(i+1)%3] += thisQueue[(i+1)%3];
                    
                    }else{
                        subQueue[i%3] += thisQueue[i%3];
                        subQueue[(i+1)%3] -= thisQueue[i%3];
                    }

                    int maxNum = Math.max(Math.max(subQueue[0], subQueue[1]), subQueue[2]);
                    int minNum = Math.min(Math.min(subQueue[0], subQueue[1]), subQueue[2]);

                    if(!visitList[maxNum][minNum]){
                        visitList[maxNum][minNum] = true;
                        bfsQueue.add(new int[] {subQueue[0], subQueue[1], subQueue[2]});
                    }
                }
            }
        }

        System.out.println(result);

    }

}