[백준] code.plus(BFS 알고리즘,JAVA)12886번, 돌 그룹

문제 링크

12886번: 돌 그룹

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

그래프 알고리즘이란?

각 정점과 연결하는 선분의 정보를 가지고 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) .... 등을 이용하여 정점에서 다른 정점으로 가는 최소값, 최대값 등의 문제에서 출력하라는 결과를 구하는 알고리즘입니다.

 

BFS?

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 돌의 그룹은 항상 3개가 주어진다.

2. 모든 그룹의 무게를 같게 만들어야 한다.

3. 모든 그룹의 무게를 같게 만들 수 있다면 1, 아니면 0을 결과로 출력한다.

 

BFS 탐색을 진행하여 모든 돌 그룹의 무게가 같아지는데 확인하였습니다.

 

BFS탐색을 진행할 때 방문 여부 확인을 저는 처음에 boolean[][][]의 3차원 형태로 확인하였지만 "메모리 초과"가 발생하였습니다.

 

생각을 해보니 2차원 배열로 방문 여부를 확인하면 나머지 값은 어차피 정해지기 때문에 상관 없다는 것을 알게되었습니다.

 

예를 들어

 

A = 20, B = 5, C = 30

 

A와 B의 돌을 움직일 때

 

A = 15, B = 10, C = 30

 

boolean[15][10]으로 방문 여부를 확인한다.

 

이유 : 모든 그룹의 전체 무게는 고정적이기 때문에 나머지 그룹의 무게는 항상 동일하기 때문입니다.

 

 

돌이 움직이는 방법은 3가지가 존재합니다.

 

A -> B

A -> C

B -> C

 

위 3가지를 BFS으로 탐색하여 동일한 무게가 나오면 1, 나오지 않으면 0을 결과로 출력하였습니다.

 

예제입력 2.

A = 1, B = 1, C = 2

 

A -> B

A = 2, B = 0, C= 2

 

visited[2][0] = true

 

A -> CA = 2, B= 1, C= 1

 

visited[2][1] = true

 

B -> CA = 1, B = 2, C = 1

 

vistied[2][1]은 벌써 방문해서 탐색 종료

 

....

모두 방문처리가 되었음에도 같은 무게가 되는 그룹을 찾지 못하였기 때문에 결과 0을 출력한다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 그룹별 무게를 저장하였습니다.
• 그룹의 돌을 이동하여 같은 무게를 만들 수 있는지 구하는 bfs함수를 실행하였습니다.
• 같은 무게를 만들 수 있다면 1, 없다면 0을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 A->B, A->C, B->C의 경우를 모두 이동하여 그룹의 무게가 같아지는지 확인하였습니다.
• bfs함수는 그룹의 돌을 움직일 때 stoneMove 함수를 이용하였습니다.
• stoneMove함수는 그룹의 무게에 따른 돌의 이동을 진행하였습니다.

 

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

public class Main {
	//그룹별 무게 저장 관련 클래스
    static class stone{
        int A,B,C;
        public stone(int a, int b, int c) {
            A = a;
            B = b;
            C = c;
        }
    }
    static boolean[][] visited;		//방문 확인 배열
    static public void  main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int stone1 = Integer.parseInt(st.nextToken());
        int stone2 = Integer.parseInt(st.nextToken());
        int stone3 = Integer.parseInt(st.nextToken());
        //전체 그룹 무게 합 구하기
        int size = stone1 + stone2 + stone3;
        if(size%3!=0)	//무게 합이 3으로 나누어 떨어지지 않으면 같은 무게로 나눌 수 없다.
            bw.write("0");
        else{
            visited = new boolean[size+1][size+1];
            //BFS 탐색 시작
            if(bfs(stone1, stone2, stone3))
                bw.write("1");	//같은 무게의 그룹으로 만들 수 있을 때
            else
                bw.write("0");	//같은 무게의 그룹으로 만들 수 없을 때
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS탐색 진행
    static boolean bfs(int a, int b, int c){
        Queue<stone> queue = new LinkedList<>();
        visited[a][b] = true;	//[A][B] 방문
        visited[b][c] = true;	//[B][C] 방문
        visited[a][c] = true;	//[A][C] 방문
        queue.add(new stone(a,b,c));
        while(!queue.isEmpty()){
            stone cur = queue.poll();
            int A = cur.A;
            int B = cur.B;
            int C = cur.C;
            if(A==B &&  B==C)	//모두 같은 무게일 때
                return true;
            stoneMove(queue, A,B,C,1);	//A->B
            stoneMove(queue, A,C,B,2);	//A->C
            stoneMove(queue, B,C,A,3);	//B->C
        }
        return false;

    }
    //돌 이동하는 함수
    static void stoneMove(Queue<stone> queue, int stone1, int stone2,int remainder, int check){
        //무게가 더 작은 그룹으로 돌 이동하기 위해 그룹별 무게 비교
        if(stone1>stone2){
            stone1 -= stone2;
            stone2 += stone2;
        }else{
            stone2 -= stone1;
            stone1 += stone1;
        }
        if(check==1){	//A->B
            if(!visited[stone1][stone2]){
                visited[stone1][stone2] = true;
                queue.add(new stone(stone1, stone2, remainder));
            }
        }else if(check==2){		//A->C
            if(!visited[stone1][stone2]){
                visited[stone1][stone2] = true;
                queue.add(new stone(stone1, remainder, stone2));
            }
        }
        else{		//B->C
            if(!visited[stone1][stone2]){
                visited[stone1][stone2] = true;
                queue.add(new stone(remainder, stone1, stone2));
            }
        }
        return;
    }
}