알고리즘 풀이 - 백준 12886(돌 그룹, 그래프(BFS, DFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

돌 그룹이 3가지 있을 때, 서로 다른 2가지를 골라서 상호 연산을 수행했을 때, 모든 그룹을 같은 개수로 만들 수 있는지 여부를 확인하는 문제

 

 

2. 풀이

 

돌 그룹은 3가지 있는데, 이를 A, B, C라고 하자. 이 때, 각 그룹 중 2가지를 골라 서로 개수가 다르면 돌의 개수를 조정하는 연산을 수행하면 된다.

따라서 돌의 개수가 다른 모든 경우의 수를 체크하여 개수를 상호 조정하며 탐색하는 전형적인 그래프 탐색 문제이다. BFS, DFS 모든 방식으로 풀어낼 수 있다.

 

초반에 이 문제를 풀기 위해서 3차원의 배열을 이용하여 이미 탐색한 돌의 그룹들을 제외해야 한다고 생각했다. 그러나 각 그룹의 범위가 최대 500이기 때문에 3차원의 배열을 만들면 메모리 초과가 발생한다.

잘 생각해보면, 돌의 전체 개수는 같으므로 2개만 처리를 하면 나머지 하나는 자동으로 정해지게 된다.

 

따라서, 2차원의 배열을 만들어 해당 돌의 그룹들이 이미 탐색되었는지를 확인하는 방식으로 탐색하여 풀어낼 수 있다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

① BFS로 풀기

import java.io.*;
import java.util.*;

public class Main{
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        
        boolean[][] visited = new boolean[1001][1001];
        int sum = A+B+C;
        
        // 돌 3개가 3으로 나누어지지 않으면 모두 같은 수가 될 수 없으니 0을 출력한다.
        if(sum % 3 != 0) {
            System.out.println(0);
            System.exit(0);
        }
        
        Queue<Group> q = new LinkedList<>();
        
        // 2개의 돌의 경우를 Queue에 넣고 시작(나머지 하나는 sum에서 빼면 된다.)
        q.offer(new Group(A, B));
        visited[A][B] = true;
        visited[B][A] = true;
        
        boolean flag = false;
        while(!q.isEmpty()){
            Group g = q.poll();
            int a = g.A;
            int b = g.B;
            int c = sum - a - b;
            
            // 모두 같아진 경우 멈춘다.
            if(a == b && b == c) {
                flag = true; break;
            }
            
            // a, b, c가 각각 다른 경우 모든 경우에 대해서 개수를 조정하고 다음 탐색을 위해 Queue에 넣는다.
            if(a != b){
                // 더 큰 수를 - 연산 하고 작은 수를 2배한다.
                int na = a > b ? a-b : 2*a;
                int nb = b > a ? b-a : 2*b;
                if(na <= 1000 && nb <= 1000 && !visited[na][nb]){
                    visited[na][nb] = true;
                    visited[nb][na] = true;
                    q.offer(new Group(na, nb));
                }
            }
            
            if(a != c){
                int na = a > c ? a-c : 2*a;
                int nc = c > a ? c-a : 2*c;
                if(na <= 1000 && nc <= 1000 && !visited[na][nc]) {
                    visited[na][nc] = true;
                    visited[nc][na] = true;
                    q.offer(new Group(na, nc));
                }
            }
            
            if(b != c){
                int nb = b > c ? b-c : 2*b;
                int nc = c > b ? c-b : 2*c;
                if(nb <= 1000 && nc <= 1000 && !visited[nb][nc]) {
                    visited[nb][nc] = true;
                    visited[nc][nb] = true;
                    q.offer(new Group(nb, nc));
                }
            }
        }
        
        
        System.out.println(flag ? 1 : 0);
        br.close();
    }
}
class Group{
    int A;
    int B;
    public Group(int A, int B){
        this.A=A;
        this.B=B;
    }
}

 

② DFS로 풀기

import java.io.*;
import java.util.*;

public class Main{
    static int sum;
    static boolean[][] visited;
    static int ans = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        
        visited = new boolean[1001][1001];
        sum = A+B+C;
        
        visited[A][B] = true;
        visited[B][A] = true;
        if(sum % 3 == 0 && dfs(A, B)){
            ans = 1;
        }
        
        System.out.println(ans);
        br.close();
    }
    
    private static boolean dfs(int a, int b){
    
        // 값이 모두 같으면 true 반환
        int c = sum - a - b;        
        if(a == b && b == c) return true;
        int[] nums = {a, b, c};
        
        boolean flag = false;
        
        // a, b, c로 3개의 값에 대해 상호 비교를 수행
        for(int i=0; i < 3; i++){
            for(int j=i+1; j < 3; j++){
                if(nums[i] != nums[j]){
                    // 더 큰 값을 -연산 처리하고 작은 값을 2배한다.
                    int ni = nums[i] > nums[j] ? nums[i] - nums[j] : nums[i]+nums[i];
                    int nj = nums[j] > nums[i] ? nums[j] - nums[i] : nums[j]+nums[j];
                    
                    // 범위 내에 있으며 이전에 체크하지 않은 경우라면
                    if(ni <= 1000 && nj <= 1000 && !visited[ni][nj]){
                        visited[ni][nj] = true;
                        visited[nj][ni] = true;
                        flag = dfs(ni, nj);
                    }
                    
                    // 만약 true가 반환되었다면 값이 모두 같은 것이므로 true 반환
                    if(flag) return true;
                }
            }
        }
        // 이전에 true가 반환되지 못했다면 false 반환
        return false;
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.