[백준] 알고리즘 분류(브루트포스 알고리즘,JAVA)15684번, 사다리 조작

문제 링크

15684번: 사다리 조작

---

 

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 가로선은 연속하거나 서로 접하면 안되며, 가로선은 점선 위에 있어야 합니다.

2. 세로선은 위에서 아래로 내려가며, 가로선을 만나면 해당 방향으로 이동합니다.

3. 가로선을 추가해서 i번째 세로선이 i번째로 내려가도록 조작을 진행해야합니다.

4. 3번을 초과하여 추가하거나, 만들 수 없으면 -1을 결과로 출력합니다.

5. 3번 이하로 가로선을 조작하여 조건에 만족할 수 있다면 최소 추가 횟수를 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 가로선을 조작할 수 있는 모든 경우를 탐색합니다.

 

3. 조건에 만족하면 최소 조작 횟수, 조건에 만족하지 않을 때 -1을 결과로 출력합니다.

 

 

가로선 조작하는 모든 경우 탐색

 

저는 가로선이 있다는 나타내기 위해서 booelan[][] 배열을 이용하였습니다.

 

아래와 같은 가로선이 추가되었을 때 

 

boolean[1][1] = true으로 설정

 

boolean[h][n]의 값 : h 높이의 (n , n + 1)의 가로선이 연결되었는지 확인합니다.

 

아래와 같은 형태일 때

boolean[1][1] = true

boolean[3][2] = true

boolean[5][4] = true

 

가로선을 조작할 때 서로 접해야 하지 않기 때문에

추가하려는 가로선에는 아래와 같은 조건을 충족해야 합니다.

 

!boolean[h][n-1] && !boolean[h][n-1]

(해석 : 좌우의 가로선이 존재하는지 확인, 존재한다면 false)

 

재귀를 통해서 각 가로선을 추가할 수 있는 모든 경우를 탐색합니다.

※재귀를 추가하는 과정은 예제입력에 대한 풀이과정에서 보실 수 있습니다.

 

가로선 조작하는 모든 경우 탐색

 

높이가 최대곳부터 시뮬레이션을 진행합니다.

높이를 방문할 때

가로선이 있을 때 : 가로선 방향으로 이동!

가로선이 없을 때 : 높이 1칸 감소하기!

 

위에 그림으로 예를들어.

 파란색 지점에서 가로선이 존재하므로 이동하기!

파란색 지점에 가로선이 존재하지 않으므로 높이 1칸 감소

 

모든 세로선을 시작!

똑같은 세로선으로 도착 :  사다리 조작 성공!

똑같은 세로선으로 1개라도 미도착 :  사다리 조작 실패!

 

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

N = 2

M = 1

H = 3

 

2. 가로선을 조작할 수 있는 모든 경우를 탐색합니다.

모든 경우 탐색

boolean[1][1] = true

boolean[2][1] = true

조건에 만족!

위에 그림대로 가로선을 추가해서 시뮬레이션을 진행해도 조건 만족!

위에 그림대로 가로선을 추가했을 때 시뮬레이션 진행하면 조건 불만족!

 

3. 조건에 만족하면 최소 조작 횟수, 조건에 만족하지 않을 때 -1을 결과로 출력합니다.

 

조건에 만족하면서 최소 조작한 횟수 : 1개

 

1을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용해서 사다리 정보들을 띄어쓰기 기준 나누었습니다.
• boolean[][]배열에 초기 가로선에 정보를 저장합니다.
• 초기 사다리 상태에서 조건에 만족하는지 확인, 불만족시 가로칸 추가하는 모든 경우 탐색합니다.
• search함수를 이용하여 가로칸을 추가하는 모든 경우를 탐색합니다.
• 모든 경우 탐색한 뒤, 조건에 만족하면 가로칸 추가하는 최소값, 불만족시 -1을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 재귀를 통해 가로선을 추가할 수 있는 모든 경우를 탐색합니다.
• gameStart함수는 사다리 타기 게임을 시뮬레이션해서 조건에 만족하는지 확인합니다.

 

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

public class Main{
    static boolean[][] check;	//가로선 확인 배열
    static int N,M,H, answer = 4;
    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 = new StringTokenizer(br.readLine()," ");
        //N, M, H 입력값 저장
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        check = new boolean[H+1][N+1];
        //초기 가로선 정보 저장
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            check[a][b] = true;	//가로선 추가!
        }
        //가로선을 추가하지 않아도 조건에 만족할 때
        if(gameStart()){
            bw.write("0");		//1개도 추가하지 않았으므로 0을 BufferedWriter 저장
        }else{
            search(1, 1, 0);	//가로선 추가하는 모든 경우 탐색
            //가로선을 3개 초과해서 사용해야 하거나 조건에 맞게 만들지 못할 때
            if(answer > 3)
                bw.write("-1");		//-1 BufferedWriter 저장
            else		//조건에 만족하는 최소 가로선 조작횟수 BufferdWriter 저장
                bw.write(answer + "");
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //가로선 추가 모든 경우를 탐색하는 재귀 함수
    static void search(int count, int y, int x){
        //가로선 추가 횟수 3번 초과 및 1번만 추가했을 때 조건에 만족할 때
        if(count > 3 || answer == 1)
            return;
        //가로선 추가하는 경우 탐색
        for(int i=x+1;i<N;i++){
            //가로선이 있거나 좌우에 인접한 가로선이 있을 때
            if(check[y][i-1] || check[y][i+1] || check[y][i])
                continue;
            check[y][i] = true;
            //가로선 추가했을 때 조건에 만족할 때
            if(gameStart()){
                answer = Math.min(answer, count);
                check[y][i] = false;
                return;
            }
            search(count+1, y, i);
            check[y][i] = false;
        }
        for(int i=y+1;i<=H;i++){
            for(int j=1;j<N;j++){
                //가로선이 있거나 좌우에 인접한 가로선이 있을 때
                if(check[i][j-1] || check[i][j+1] || check[i][j])
                    continue;
                check[i][j] = true;
                //가로선 추가했을 때 조건에 만족할 때
                if(gameStart()){
                    answer = Math.min(answer, count);
                    check[i][j] = false;
                    return;
                }
                search(count+1, i, j);
                check[i][j] = false;
            }
        }
    }
    //사다리 게임 시뮬레이션 진행하는 함수
    static boolean gameStart(){
        //각 세로선 탐색
        for(int i=1;i<=N;i++){
            int height = H;	//최대 높이
            int position = i;	//현재 위치
            //시뮬레이션 진행
            while(height>0){
                //왼쪽 가로선 존재시
                if(check[height][position-1]){
                    position--;
                    height--;
                    continue;
                }
                //오른쪽 가로선 존재시
                if(check[height][position])
                    position++;
                height--;	//높이 감소
            }
            //세로선이 도착했을 때 동일하지 못할 경우 시뮬레이션 종료!
            if(position != i)
                return false;
        }
        return true;	//조건에 만족할 때
    }
}