[성실코딩 9일차] 백준 #9207 페크 솔리테어 / DFS, BFS

연구소랑 유사한 문제. DFS랑 BFS 섞어서 푸는 문제. 

이번년도 하반기 삼성 코테에서도 두 번째 문제가 이런 유형이었는데 

코테 보고 오니까 이런 유형이 많이 보이네 ~,~

나는 이런 문제를 계속 함수 두 개 만들어서 함수에서 함수 부르는 구조로 품. 

이게 최적의 방법인지 모르겠음

"문제 풀이"

<dfs1 함수>에서 전체 map을 확인하며 'o' 이 있는 곳 찾음. -> [dfs 함수] 호출

[dfs 함수]에서는 시작 위치 'o'에서부터 상하좌우 점프 가능한 곳 이동하고, 이동한 맵에서 다시 <dfs1 함수> 호출 -> 이게 return 받으면 다시 이동한 거 초기화

---

#include<iostream>

using namespace std;

char board[5][9];

int move_cnt = 0;
int pin_num = 0;

int smallest_pin_num = 0;
int smallest_move_cnt = INT8_MAX; // 백준에선 INT_MAX 사용 -> 컴파일 에러

// 상하좌우
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

void dfs1();

void dfs(int _x, int _y) {

	for (int k = 0; k < 4; k++) {
		int x = _x + dx[k];
		int y = _y + dy[k];
		int new_x = x + dx[k];
		int new_y = y + dy[k];

		if ( (x<0 || x>4) || (y<0 || y>8) 
			|| (new_x<0 || new_x>4)
			|| (new_y<0 || new_y>8) ) { // 범위를 벗어나면 continue
			continue;
		}
		if (board[x][y]=='o' && board[new_x][new_y]=='.') { // 핀있으면 뛰어 넘을 수 잇음
			
			board[_x][_y] = board[x][y] = '.';
			board[new_x][new_y] = 'o';
			pin_num--;
			move_cnt++;
			
			dfs1();

			pin_num++;
			move_cnt--;
			board[_x][_y] = board[x][y] = 'o';
			board[new_x][new_y] = '.';
		}
	}
}

void dfs1() {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 9; j++) {
			if (board[i][j] == 'o') {
				dfs(i, j);
			}
		}
	}
	// 반복문 다 돌고, 재귀도 다 돌고 나왔다는 것은 
	// 더 이상 이동할 수 있는 핀이 없음
	if (smallest_pin_num == pin_num && smallest_move_cnt>move_cnt) {
		smallest_pin_num = pin_num;
		smallest_move_cnt = move_cnt;
	}
	else if (smallest_pin_num>pin_num) {
		smallest_pin_num = pin_num;
		smallest_move_cnt = move_cnt;
	}
}

int main() {

	int tc;
	cin >> tc;

	for (int i = 0; i < tc; i++) {
		
		// 입력받기
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 9; j++) {
				char temp;
				cin >> temp;
				
				if (temp=='o') {
					pin_num++;
					smallest_pin_num++;
				}
				board[i][j] = temp;
			}
		}

		// 연산
		dfs1();

		// 출력
		cout << smallest_pin_num << " " << smallest_move_cnt << endl;
	
		// 초기화
		move_cnt = 0;
		pin_num = 0;

		smallest_pin_num = 0;
		smallest_move_cnt = INT8_MAX;
	}
	return 0;
}