[레이튼 미스터리저니] 이쪽저쪽 프루트

레이튼 미스터리저니 홈화면

요즘 출퇴근 할 때마다 자주 하는 모바일 게임으로 레이튼 미스터리저니 - 일곱 대부호의 음모를 하고 있다.

지금은 모든 스토리를 진행하고, 비밀 모드로 수수께끼를 풀고 있는데, 한 파트가 진행하는데 너무 오랜 시간이 걸려 

알고리즘을 통해 문제의 답을 도출하는 프로그램을 짜려고 한다.

 

이쪽저쪽 프루트

비밀모드-일간수수께끼 통신 모습

이쪽저쪽 프루트는 비밀모드-일간수수께끼 통신 중 한 수수께끼 장르로

이미 고정된 과일의 배치를 참고하여 정해진 규칙에 따라 과일가게의 배치를 지정해야 한다.

일간 수수께끼 통신의 이쪽저쪽 프루츠

규칙은 다음과 같다.

이쪽저쪽 프루츠 규칙

1. 과일의 종류는 4가지 이다 ( 사과,포도,바나나,메론)

2. 8x8 타일 내에 가로줄, 세로줄에 과일의 종류가 각각 2개씩 들어간다.

3. 연속해서 같은 종류의 과일을 배치할 수 없다.

 

문제 풀이

 

일종의 스도쿠나 마방진 문제와 비슷하다.

8x8의 적은 타일 수가 주어져 있음으로 완전탐색 및 백트래킹을 사용하였다.

 

1) 입력

- 문제를 입력한다. 입력을 편하게 하기 위해 {사과 : 1, 포도 : 2, 바나나 : 3, 메론 4} 로 지정하였다.

2) 완전탐색

 - 빈 공간에 과일을 순서대로 넣어본 뒤, 조건에 맞다면 dfs를 실시한다.

3) 조건검사

 - 현재 행과 열에 대해서 알맞은 조건인지 검사를 실시한다.

 a. 행과 열이 보드판 내부에 있는지?

 b. 같은 과일이 붙어있지 않은지?

 c. 가로열에 같은 과일 종류가 2개가 넘지 않는지?

 d. 세로열에 같은 과일 종류가 2개가 넘지 않는지?

 - 모든 조건을 통과 시 true, 아닐 시 false

4) 출력

- 답을 출력한다. (사과 : 사, 포도 : 포, 바나나 : 바, 메론 : 메)

 

코드는 다음과 같다.

package 레이튼;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 이쪽저쪽프루츠 {
	//게임 보드
	static int[][] Board;
	static int[][] D = {{0,1},{0,-1},{1,0},{-1,0}};
	static boolean IsFindAnswer= false;
	
	//빈공간 : 0, 사과 1, 포도 2, 바나나 3, 메론 4
	static String[] Fruits= {"□","사","포","바","메"};
	
	public static void findAnswer(int r, int c) {
		//r이 8에 도달하는 경우에는 답이다.
		if(r>=8) {
			IsFindAnswer = true;
			return;
		}
		int fruit = Board[r][c];
		//빈공간 이라면
		if(fruit==0) {
			//과일을 다 넣어본다
			for(int i=1;i<5;i++) {
				Board[r][c]=i;
				//알맞는 과일이라면(조건검사) 
				if(isRightFruit(r, c)) {
					//다음 요소 진행
					int nc = c+1; //열 증가
					int nr = r;
					//열이 8 이상이라면
					if(nc>=8) {
						nr++; //행 증가
						nc = 0; //열 0으로 초기화
					}
					findAnswer(nr, nc);
					//답을 찾았다면 종료
					if(IsFindAnswer) break;
				}
			}
		//과일이 있다면
		}else {
			//다음 탐색
			int nc = c+1;
			int nr = r;
			if(nc>=8) {
				nr++;
				nc = 0;
			}
			findAnswer(nr, nc);
		}
		//답을 찾지 못하였다면 종료시 원복
		if(!IsFindAnswer) {
			Board[r][c]=fruit;
		}
	}
	
	public static void printBoard() {
		//출력
		System.out.println("답입니다.");
		for(int i=0;i<8;i++) {
			for(int j=0;j<8;j++) {
				System.out.print(Fruits[Board[i][j]]+" ");
			}
			System.out.println();
		}
		System.out.println();
	};
	
	//유효한지 검사
	public static boolean isRightFruit(int r, int c) {
		int fruit= Board[r][c];
		//연속 같은 과일 배치 불가
		for(int i=0;i<4;i++) {
			int nr = r+D[i][0];
			int nc = c+D[i][1];
			//범위밖 제외
			if(nr<0||nr>=8||nc<0||nc>=8) continue;
			//주변과 동일한 과일이라면 false
			if(fruit==Board[nr][nc]) return false;
		}
		//라인에 같은 종류 과일이 꼭 2개이어야 함
		//빈공간 : 0, 사과 1, 포도 2, 바나나 3, 메론 4
		int[] counts = new int[5];
		//a. 가로
		for(int i=0;i<8;i++) {
			counts[Board[r][i]]++;
		}
		//빈공간 제외하고 다른 과일이 2를 넘으면 false;
		for(int i=1;i<5;i++) {
			if(counts[i]>2) return false;
		}
		//b. 세로
		counts = new int[5]; //초기화
		for(int i=0;i<8;i++) {
			counts[Board[i][c]]++;
		}
		//빈공간 제외하고 다른 과일이 2를 넘으면 false;
		for(int i=1;i<5;i++) {
			if(counts[i]>2) return false;
		}
		//모두 통과시 true
		return true;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//보드 입력
		System.out.println("주어진 과일 배치를 입력해주세요");
		System.out.println("빈공간 : 0, 사과 1, 포도 2, 바나나 3, 메론 4");
		System.out.println("한 줄 예) 30400010");
		//빈공간 : 0, 사과 1, 포도 2, 바나나 3, 메론 4
		Board= new int[8][8];
		for(int i=0;i<8;i++) {
			String line = br.readLine();
			for(int j=0;j<8;j++) {
				Board[i][j]=Integer.parseInt(line.charAt(j)+"");
			}
		}
		//문제 풀이
		findAnswer(0,0);
		//출력
		printBoard();
		br.close();
	}
}

실제 적용

실제 문제를 이용하여 답을 잘 찾는지 확인해보자

 

실제 문제를 가져왔다.

주어진 과일 배치를 프로그램에 입력한다.

위의 그림을 입력한 모습

결과는 다음과 같다.

도출한 답의 모습

도출된 답을 입력한 모습

결과는??

문제해결! 손찌검은 기분나쁘지만 어쨌든 기쁘다

즐거워하는 모습을 보니 나도 춤을 추고 싶다.

문제 해결!

 

실생활에서 알고리즘을 이용하면 이처럼 빠른 속도로 문제를 해결할 수 있다.