[백준] code.plus(브루트포스 - 재귀,JAVA)16197번, 두 동전

문제 링크

16197번: 두 동전

---

주의사항

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

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

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

이 문제에 핵심은

1. 코인은 항상 2개가 주어집니다.

2. 코인이 하나만 떨어뜨려야만 게임이 종료됩니다.

3. 코인이 이동할 때 벽이면 이동하지 않는다.

4. 버튼을 10번 이상 눌렀을 때에는 -1을 결과로 출력합니다.

 

코인을 상/하/좌/우 이동하는 것을 재귀로 구현하였으며

 

코인이 가장 먼저 1개가 떨어질 때에 버튼을 누른 횟수를 출력해야 한다.

 

만약 버튼을 누른 횟수가 10번 넘어갔을 때 -1을 결과로 출력해야 한다.

 

예제 입력 2에서 대입해보면

상/하/좌/우 순으로 이동하며 '상'을 먼저 이동합니다.

.	#
.	#
.	#
0	#
0	#
#	#

∴좌로 이동하면 2개의 코인이 떨어지기 때문에 좌로 이동할 수는 없습니다.

.	#
.	#
0	#
0	#
.	#
#	#

상/하/좌/우 순으로 이동하며 '상'을 먼저 이동합니다.

.	#
0	#
0	#
.	#
.	#
#	#

상/하/좌/우 순으로 이동하며 '상'을 먼저 이동합니다.

0	#
0	#
.	#
.	#
.	#
#	#

상/하/좌/우 순으로 이동하며 '상'을 먼저 이동합니다.

0	#
.	#
.	#
.	#
.	#
#	#

코인 1개가 떨어졌기 때문에 버튼을 누른 횟수가 4가 됩니다.

 

다른 방식의 버튼 누른 횟수를 확인하면

→↑↑↑↑ = 5번 누르면 동일하게 나옵니다.

....

 

모든 재귀가 끝난 뒤 최소 누른 횟수를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 게임판에 대한 정보를 저장하였습니다.
• 게임을 진행하여 버튼을 누른 횟수를 얻는 game 함수를 실행하였습니다.
• 버튼 누른 횟수가 10번보다 많으면 -1, 아니면 최소 누른 횟수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• game함수는 2개의 코인을 상하좌우 이동하며 1개의 코인이 떨어질 때 버튼 횟수를 구합니다.
• boardIn함수는 코인이 이동했을 경우 게임판 안에 존재하는지 확인하는 함수
• boardMove함수는 코인이 이동했을 경우 벽으로 이동하는지 확인하는 함수

 

import java.io.*;
import java.util.*;
public class Main {
	static int N,M,result = 11;
	static char[][] board;		//게임판 저장 배열
	static int[] dx = {0,0,-1,1};	//상하좌우 x값 변경값
	static int[] dy = {-1,1,0,0};	//상하좌우 y값 변경값
	static int[][] coin = new int[2][2];
    public static 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()," ");
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	int index = 0;
    	board = new char[N][M];
        //게임판의 대한 정보를 저장
    	for(int i=0;i<N;i++) {
    		String str = br.readLine();
    		for(int j=0;j<M;j++) {
    			board[i][j] = str.charAt(j);
    			if(str.charAt(j)=='o') {
    				coin[index][0] = j;
    				coin[index++][1] = i;
    			}	
    		}
    	}
    	game(coin[0][0],coin[0][1],coin[1][0],coin[1][1],1);	//게임 시작
    	if(result==11)		//버튼 누른 횟수가 10회보다 더 많을 때
    		bw.write("-1\n");
    	else		//10회 이하일 때 누른 최소 횟수 BufferedWriter 저장
    		bw.write(result + "\n");
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //게임 진행하는 함수
    static void game(int x1, int y1, int x2, int y2, int count) {
    	if(count>10) 
    		return;
    	for(int i=0;i<4;i++) {	
        	//2개의 코인 상하좌우 순으로 이동
    		int coin1_x = x1 + dx[i];
    		int coin1_y = y1 + dy[i];
    		int coin2_x = x2 + dx[i];
    		int coin2_y = y2 + dy[i];
            	//2개의 코인이 떨어질 때
    		if((boardIn(coin1_y, true) ^ boardIn(coin1_x, false)) &&
    				(boardIn(coin2_y, true) ^ boardIn(coin2_x, false))) {
    			continue;
            	//1개의 코인이 떨어질 때
    		}else if((boardIn(coin1_y, true) ^ boardIn(coin1_x, false)) ^
    				(boardIn(coin2_y, true) ^ boardIn(coin2_x, false))) {
    			result = Math.min(result, count);
    			return;
    		}
            	//2개의 코인 이동시 벽에 걸리지 않을 때
    		if(boardMove(coin1_x,coin1_y) && boardMove(coin2_x, coin2_y))
    			game(coin1_x,coin1_y,coin2_x,coin2_y,count+1);
           		//1번째 코인이 벽에 걸릴때
    		else if(boardMove(coin1_x,coin1_y) && !boardMove(coin2_x, coin2_y))
    			game(coin1_x,coin1_y,x2,y2,count+1);
            	//2번째 코인이 벽에 걸릴 때
    		else if(!boardMove(coin1_x,coin1_y) && boardMove(coin2_x, coin2_y))
    			game(x1,y1,coin2_x,coin2_y,count+1);
    	}
    	return;
    }
    //이동시 보드 안에 존재하는지 확인하는 함수
    static boolean boardIn(int value, boolean check) {
    	if(value>=0) {
    		if(check) {
    			if(value<N)
    				return false;
    		}else {
    			if(value<M)
    				return false;
    		}
    	}
    	return true;
    }
    //보드 이동한 지점이 벽인 경우 확인하는 함수
    static boolean boardMove(int x, int y) {
    	if(board[y][x]!='#') 
    		return true;
    	
    	return false;
    }
}