[백준] code.plus(BFS 알고리즘,JAVA)12906번, 새로운 하노이 탑

문제 링크

12906번: 새로운 하노이 탑

---

주의사항

• 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. 막대기의 가장 위에 있는 원판을 움직일 수 있습니다.

2. 게임의 목표에 도달하는 최소 원판 이동 횟수를 결과로 출력합니다.

3. 게임의 목표는 막대 A에는 A원판만, 막대 B에는 B원판만, 막대 C에는 C원판만 존재할 때입니다.

 

알고리즘 진행 순서.

 

1. 초기 상태 코드와 정답이 되는 상태 코드를 구한다.

 

2. 원판의 이동을 BFS탐색으로 진행하여 정답이 되는 상태 코드와 동일할 때 원판의 최소 이동 횟수를 구해서 출력한다.

 

 

상태 코드

 

현재 각 막대기의 상태를 표현하는 코드입니다.

막대기별 상태를 나누기 위해서 " "(띄어쓰기)를 통해서 나누었습니다.

 

정답이 되는 상태 코드는 게임의 목표를 도달했을 때 각 막대기의 상태를 표현한 코드입니다.

 

예제입력2.

 

초기 상태 코드

B C A

 

정답이 되는 상태 코드

A B C

 

상태 코드를 이용해서 하노이 게임의 BFS탐색에 방문 처리를 확인하였습니다.

 

방문 처리를 위해 상태 코드들을 HashSet에 저장하여 contains을 이용해서 방문하였는지 확인하였습니다.

 

 

예제입력 1.

 

1. 초기 상태 코드와 정답이 되는 상태 코드를 구한다.

 

초기 상태 코드

A AA AA

 

정답이 되는 상태 코드

AAAAA  

 

2. 원판의 이동을 BFS탐색으로 진행하여 정답이 되는 상태 코드와 동일할 때 원판의 최소 이동 횟수를 구해서 출력한다.

 

 AAA AA

 AA AAA

AA A AA

A A AAA

AA AA A

A AAA A

....

AAAAA  

 

과정.

AA A AA

AAA A A

AAAA  A

AAAAA  

 

원판 최소 이동 횟수 4을 결과로 출력한다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 하노이 탑에 대한 정보를 저장하였습니다.
• 초기 상태 코드, getAnswerCode를 실행하여 얻은 정답이 되는 상태 코드를 구합니다.
• gameStart를 실행시켜 게임 목표에 도달하는 원판 최소 이동 횟수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• gameStart는 BFS탐색을 통해서 원판을 이동하며 정답이 되는 상태코드에 도달하는 최소 이동횟수를 구하는 함수입니다.
• getAnswerCode은 aCount, bCount, cCount를 통해서 정답이 되는 상태 코드를 구하는 함수입니다.

 

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

public class Main {
	//하노이 상태 관련 클래스
    static class hanoiInfo{
        int count = 0;		//원판 이동 횟수
        Stack<Character> A = new Stack<>();		//막대 A
        Stack<Character> B = new Stack<>();		//막대 B
        Stack<Character> C = new Stack<>();		//막대 C
        //해당 막대 비어있는지 확인
        public boolean emptyCheck(int index){
            if(index==0){
                return A.isEmpty();
            }else if(index==1){
                return B.isEmpty();
            }else{
                return C.isEmpty();
            }
        }
        //막대기 상태 복사하기
        public void stackClone(Stack<Character> stack1, Stack<Character> stack2, Stack<Character> stack3){
            A = stack1;
            B = stack2;
            C = stack3;
        }
        //막대기에 원판 저장하기
        public void stackAdd(int index, Character stencil){
            if (index==0)
                A.add(stencil);
            else if(index==1)
                B.add(stencil);
            else
                C.add(stencil);
        }
        //막대기에 원판 빼기
        public Character stackPop(int index){
            if(index==0)
                return A.pop();
            else if(index==1)
                return B.pop();
            else
                return C.pop();
        }
        //현재 막대기 상태 코드 구하기
        public String getState(){
            String state = "";
            state += SetStencil(A);
            state += SetStencil(B);
            state += SetStencil(C);
            return state;
        }
        //막대기 원판에 대한 정보 얻기
        public String SetStencil(Stack<Character> stack){
            StringBuilder state = new StringBuilder();
            for (Character character : stack)
                state.append(character);
            state.append(" ");
            return state.toString();
        }
    }
    static HashSet<String> visited = new HashSet<>();
    static hanoiInfo basic = new hanoiInfo();	//초기 막대기 상태
    //초기 원판 A,B,C 개수, 최소 이동 횟수 저장 변수
    static int aCount, bCount, cCount, answer;
    static String answerCode;	//정답이 되는 상태 코드 저장 변수
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        //초기 하노이 상태 저장
        for(int i=0;i<3;i++){
            st = new StringTokenizer(br.readLine()," ");
            int n = Integer.parseInt(st.nextToken());
            if(n==0)
                continue;
            String stencil = st.nextToken();
            for(int j=0;j<n;j++){
                char temp = stencil.charAt(j);
                if(temp=='A')	//원판 A일 때
                    aCount++;
                else if(temp =='B')	//원판 B일 때
                    bCount++;
                else if(temp == 'C')	//원판 C일 때
                    cCount++;
                basic.stackAdd(i, temp);	//막대기에 원판 저장하기
            }
        }
        visited.add(basic.getState());	//초기 상태 코드 HashSet 저장
        answerCode = getAnswerCode();	//정답이 되는 상태 코드 구하기
        answer = gameStart();	//하노이 게임 시작!
        bw.write(answer + "");	//최소 이동 횟수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS탐색으로 하노이 게임을 진행하는 함수
    static int gameStart(){
        Queue<hanoiInfo> queue = new LinkedList<>();
        queue.add(basic);	//초기 상태 Queue 저장
        while(!queue.isEmpty()){
            hanoiInfo cur = queue.poll();
            if(cur.getState().equals(answerCode))	//게임 목표 도달!
                return cur.count;
            for(int i=0;i<3;i++){
                if(!cur.emptyCheck(i)){
                    for(int j=0;j<3;j++){
                        if(i!=j){
                            //원판 이동하기
                            char temp = cur.stackPop(i);
                            cur.stackAdd(j,temp);
                            String state = cur.getState();
                            if(!visited.contains(state)){	//방문하지 않았던 상태 코드일 때
                                visited.add(state);
                                hanoiInfo tempHanoi = new hanoiInfo();
                                tempHanoi.stackClone((Stack<Character>) cur.A.clone(), (Stack<Character>) cur.B.clone(), (Stack<Character>) cur.C.clone());
                                tempHanoi.count = cur.count + 1;
                                queue.add(tempHanoi);
                            }
                            //원판 되돌리기
                            cur.stackAdd(i, temp);
                            cur.stackPop(j);
                        }
                    }
                }
            }
        }
        return -1;
    }
    //정답이 되는 상태 코드 구하는 함수
    static String getAnswerCode(){
        String result =
                "A".repeat(aCount) + " " +
                "B".repeat(bCount) + " " +
                "C".repeat(cCount) + " ";
        return result;
    }
}