[재귀] 두 동전 16197 ○

문제 해설 및 주의사항

 

적용한 레시피 / 방법론 + 접근법

 

풀이

1. 경우의 수.

- 위아래오른왼 4가지 경우가 있고, 최대 10까지만 지켜보므로, 4^10이다. 충분히 가능함.

2. 신경써야 할 조건들

- 10번 초과해 누르면 -1 

- 둘 다 떨어지면 -1

- 각 동전의 다음 좌표 설정 방법

풀이코드

#include <iostream>
#include <algorithm>
using namespace std;
// 16197 두 동전

int n, m;
// 빈 칸은 0 벽은 1
int board[20][20];

int dy[] = {0, 0, 1, -1};
int dx[] = {-1, 1, 0, 0};

bool checkCoord(int y, int x){
	if(y < 0 || y >= n || x < 0 || x >= m) return false;
	return true;
}

int solve(int y1, int x1, int y2, int x2, int count){
	// 기저사례 : 버튼을 10번 초과로 누르면 return
	if(count == 11) return -1;
	// 기저사례 : 
	bool fall1 = false, fall2 =false;
	 if (y1 < 0 || y1 >= n || x1 < 0 || x1 >= m) fall1 = true;
	 if (y2 < 0 || y2 >= n || x2 < 0 || x2 >= m) fall2 = true;
	 if (fall1 && fall2) return -1;
	 if (fall1 || fall2) return count;

	int ans = -1;
	
	for(int i = 0; i < 4; i++){
		int nx1, ny1, nx2, ny2;
		
		ny1 = y1 + dy[i];		
		nx1 = x1 + dx[i];
		ny2 = y2 + dy[i];		
		nx2 = x2 + dx[i];
		
		if(checkCoord(ny1, nx1)){
			// 범위 안에 들고, 벽 이라면
			if(board[ny1][nx1] == 1){
				ny1 = y1;
				nx1 = x1;	
			}	
		}
		
		if(checkCoord(ny2, nx2)){
			// 범위 안에 들고, 벽 이라면
			if(board[ny2][nx2] == 1){
				ny2 = y2;
				nx2 = x2;	
			}	
		}
		
		
		int tmp = solve(ny1, nx1, ny2, nx2, count + 1);
		if(tmp != -1){
			if(ans == -1 || ans > tmp){
				ans = tmp;
			}
		}
	}
	return ans;
}

int main(){
	cin >> n >> m;

	int coord[2][2];
	int count = 0;
	for(int y = 0; y < n; y++){
		string tmp;
		cin >> tmp;
		for(int x = 0; x < m; x++){
			char tmpCh;
			tmpCh = tmp[x];
			if(tmpCh == 'o'){
				coord[count][0] = y;
				coord[count][1] = x;
				count++;
			}
			else if(tmpCh == '.'){
				board[y][x] = 0;
			}
			else if(tmpCh == '#'){
				board[y][x] = 1;
			}
		}
	}
	printf("%d\n", solve(coord[0][0], coord[0][1], coord[1][0], coord[1][1], 0));
	
	
}

 

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점