16988_Baaaaaaaaaduk2_Easy ( BFS, BackTracking )

본 포스팅은 문제에 대한 접근에 문제가 없지만 코드를 구현함에 있어서 어려운 분들에게 도움이 되었으면 하고자하여 작성하게 되었습니다.

 

16988_Baaaaaaaaaduk2_Easy 

 - 이 문제는 조합으로 나오는 모든 경우에 대해 BFS 탐색을 이용해 풀 수 있는 문제이다

 - 입력으로 주어진 바둑판 상황에 대해 "검은 돌을 두개 놓을 수 있는" 모든 경우에 대해 구하고(조합), 각 상황에 따라 흰돌 (상대의 돌)이 죽는 상황인지, 죽는다면 몇개 죽는지에 대해 BFS탐색으로 확인을 해주어 풀 수 있다.

 - 문제 풀이는 BFS와 백트래킹을 활용하여 풀이했다.

 - 자세한 내용은 코드의 주석을 참고하자.

 

 

 

	//BFS와 BackTracking을 이용해 풀 수 있는 문제
	//문제의 요지는 다음과 같다
	//1. 입력으로 주어지는 바둑판은 고정된다.
	//2. 고정된 바둑판에 2개의 수를 놓을 수 있다.
	//3. 내가 임의로 2개의 수를 놓게 되었을 때, 상대방을 가장 많이 잡을 수 있는 경우를 찾아라
	//4. 상대방을 잡는 조건은 상대방이 나에게 둘러쌓여 더이상 연결된 바둑돌을 놓을 수 없는 상태이다.
	#include <iostream> //io
	#include <queue> //queue
	#include <cstring> //memset
	using namespace std;
	//바둑판 크기 변수 선언 및 초기화
	int N = 0, M = 0;
	//바둔판 배열 선언 및 초기화
	int map[20][20] = { 0 };
	//내가 놓을 바둑판의 위치에 대해 중복 방문을 확인할 배열 선언 및 초기화
	int check[20][20] = { 0 };
	//상대방이 놓은 돌을 탐색할 때 중복 방문을 확인할 배열 선언 및 초기화
	int check_black[20][20] = { 0 };
	//탐색 시 사용할 4방위 배열 선언 및 초기화 , 우 하 좌 상
	int dx[4] = { 1,0,-1,0 };
	int dy[4] = { 0,1,0,-1 };
	//bfs 탐색을 위한 큐 선언
	queue<pair<int, int>> bfs_q;
	//결과를 출력할 변수 선언 및 초기화
	int res = 0;
	//func : 내가 돌을 둔 이후 상대방의 돌을 잡을 수 있는지 판단하기 위한 함수
	//param x,y : 탐색 시작 위치
	int black_bfs(int x, int y)
	{
	//내가 잡을 수 있는 흑돌의 개수를 저장할 변수 선언 및 초기화
	//흑돌 위치에서 시작하기 초기값은 1로 시작
	int get_black_num = 1;
	//탐색 도중 0을 만났을 시 get_black_num을 반환하지 않게 하기 위한 변수
	//0을 만나고 바로 함수를 return할 수도 있찌만
	//그 경우 남은 상대돌(2)에 대해 재탐색을 해야함과 그에 맞는 조건을 새로 짜주어야하기 때문
	bool is_move = false;
	//현재 위치에 대해 방문했음을 표시
	check_black[y][x] = true;
	//현재 위치를 큐에 사입
	bfs_q.push(make_pair(x, y));
	//큐에 탐색 노드가 없을때까지 루프
	while (!bfs_q.empty())
	{
	//탐색할 노드의 정보를 가져온다
	int x = bfs_q.front().first;
	int y = bfs_q.front().second;
	//사용한 노드는 반납
	bfs_q.pop();
	//현재 위치에 대해 4방위로 탐색
	for (int i = 0; i < 4; i++)
	{
	//다음 탐색 위치에 대해 값 설정
	int xn = x + dx[i];
	int yn = y + dy[i];
	//다음 탐색 위치가 범위를 벗어나면 continue
	if (xn < 0 || xn >= M || yn < 0 || yn >= N) continue;
	//상대방 돌이 움직일 수 있다면
	//is_move를 true로 바꾸어 흑돌의 개수를 반환하지 않을 수 있게 한다
	if (map[yn][xn] == 0)
	{
	is_move = true;
	}
	//연결된 흑돌이 존재한다면 다음 탐색지점으로 정하고, 잡을 수 있는 흑돌의 개수를 증가시킨다
	else if (map[yn][xn] == 2 && check_black[yn][xn] == false)
	{
	check_black[yn][xn] = true;
	bfs_q.push(make_pair(xn, yn));
	get_black_num++;
	}
	}
	}
	//탐색 도중 0을 만난적이 없을 시 탐색한 상대방 돌의 수를 반환
	if (!is_move) return get_black_num;
	//탐색 도중 0을 만났다면 0을 반환
	return 0;
	}
	//func : 내가(1) 돌을 놓을 때 사용할 함수
	void play_go(int x, int y, int cnt)
	{
	//내가 돌을 2개 놓았다면
	if (cnt == 2)
	{
	//탐색 결과를 반환받을 변수 선언 및 초기화
	int get_black_num = 0;
	//바둑판의 모든 위치에 대해 상대 돌이 존재하는지 루프
	for (int i = 0; i < N; i++)
	{
	for (int j = 0; j < M; j++)
	{
	//바둑판에서 상대 돌을 발견하였고 아직 탐색하지 않은 돌이라면
	if (map[i][j] == 2 && check_black[i][j] == false)
	{
	//bfs탐색을 통해 상대 돌의 상태에 따라 결과값을 반환받는다
	get_black_num += black_bfs(j, i);
	}
	}
	}
	//반환받은 결과가 이전 결과보다 크다면 출력 결과 변수에 저장
	if (res < get_black_num)
	res = get_black_num;
	//현재 바둑판에 대해 탐색을 마쳤고, 이후 재탐색을 위해 방문표시 배열을 초기화
	memset(check_black, 0, sizeof(check_black));
	return;
	}
	//바둑판의 모든 위치에 대해 돌을 놓을 수 있는지 루프
	for (int i = 0; i < N; i++)
	{
	for (int j = 0; j < M; j++)
	{
	//빈 공간이며 아직 조합상 돌을 놓아보지 않은 위치라면
	if (map[i][j] == 0 && check[i][j] == false)
	{
	//현재 위치에 대해 돌을 놓아보았음을 표시
	check[i][j] = true;
	//돌이 있음을 표시
	map[i][j] = 1;
	//다음 돌을 놓거나 bfs탐색으로 이어지도록 함수 호출
	play_go(j, i, cnt + 1);
	//돌을 모두 놓고 bfs탐색이 끝났다면 돌을 회수
	check[i][j] = false;
	map[i][j] = 0;
	}
	}
	}
	}
	int main(void)
	{
	//바둑판 크기 정보를 가져온다
	cin >> N >> M;
	//바둑판의 배열 상태를 받아온다
	for (int y = 0; y < N; y++)
	{
	for (int x = 0; x < M; x++)
	{
	//받은 바둑판 배열 상태를 저장
	cin >> map[y][x];
	}
	}
	//바둑판에 대해 탐색 시작
	play_go(0, 0, 0);
	//결과 반환
	cout << res << endl;
	return 0;
	}

view raw 16988_Baaaaaaaaaduk2_Easy.cpp hosted with ❤ by GitHub