이것 저것 &

출처: https://www.acmicpc.net/problem/21608

구현문제입니다.

1. 단순구현으로 해결했다.

결론적으로 반복문을 통해서 각각의 학생들의 자리를 픽스시켜 주면 되기 때문에, 천천히 조건에 맞게 구현하면 된다.

2. 3가지 조건중 1번, 2번을 통해서 각각의 학생별로 해당하는 위치를 도출했다. 3번은 우선순위에 의해서 일반적인 반복문을 사용하면 자동으로 결정됨.

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

그런데 왠 런타임 에러??

주의점은 만약 좋아하는 친구와, 빈칸 모두 없는 상황일때는 3번 조건에 의해서 가장 가까운 칸을 선택하도록 예외처리를 추가해주어야 한다. (본 코드 storePosition 함수 아래쪽 참고)

정답 코드

#include <iostream>
#include <vector>
using namespace std;

vector <int> friends[401];
vector <int> vec; // 순서저장
int arr[25][25] = { 0, }; // 위치가 픽스 되면
int n = 0;
int result = 0;

int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };

void storePosition(int& y, int& x, int v) {


	int rf = 0;
	int rb = 0;
	int ry = 0;
	int rx = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j] != 0)
				continue;

			int cy = i;
			int cx = j;
			int fav = 0;
			int bla = 0;


			for (int k = 0; k < 4; k++) {
				int ny = cy + y_ar[k];
				int nx = cx + x_ar[k];

				if (ny < 1 || ny > n || nx < 1 || nx > n)
					continue;

				for (int u = 0; u < 4; u++) {
					if (arr[ny][nx] == friends[v][u])
						fav++;
					else if(arr[ny][nx] == 0)
						bla++;
				}
			}

			if (fav > rf) {
				rf = fav;
				rb = bla;
				ry = cy;
				rx = cx;
			}
			else if (fav == rf) {
				if (bla > rb) {
					rb = bla;
					ry = cy;
					rx = cx;
				}
			}

		}
	}



	if (ry == 0 && rx == 0) { // 중요
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (arr[i][j] == 0) {
					ry = i, rx = j;
					break;
				}
			}
			if (ry != 0 && rx != 0)
				break;
		}

	}

	y = ry, x = rx;

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;

	for (int i = 0; i < n*n; i++) {
		int temp;
		int temp2[4];

		cin >> temp;
		vec.push_back(temp);

		for (int j = 0; j < 4; j++) {
			cin >> temp2[j];
			friends[temp].push_back(temp2[j]);
		}
	}


	for (int i = 0; i < n*n; i++) {
		int v = vec[i];
		int y = 0; int x = 0;
		storePosition(y, x, v);
		arr[y][x] = v;



	}


	// 점수 계산 

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {

			int cy = i;
			int cx = j;
			int cnt = 0;

			for (int k = 0; k < 4; k++) {
				int ny = cy + y_ar[k];
				int nx = cx + x_ar[k];

				if (ny < 1 || ny > n || nx < 1 || nx > n)
					continue;

				for (int u = 0; u < 4; u++) {
					if (arr[ny][nx] == friends[arr[cy][cx]][u])
						cnt++;
				}

			}

			if (cnt == 1)
				result += 1;
			else if (cnt == 2)
				result += 10;
			else if (cnt == 3)
				result += 100;
			else if (cnt == 4)
				result += 1000;
		}
	}

	cout << result << endl;


	return 0;
}

문제링크: https://www.acmicpc.net/problem/16918

구현문제입니다.

접근방식

1. 단순구현으로 해결

3. 값이 짝수일때, 홀수일때로 나눠서 풀었다.

4. 짝수일때는 항상 모든 값이 O 

홀수일때는 값이 변화하는 것을 시뮬레이션으로 구현

문제풀이 

1. 짝수일때는 항상 모든 값이 O 

홀수일때는 값이 변화하는 것을 시뮬레이션으로 구현

2. 홀수일때, copyed배열을 만들어서 변화하는 값을 저장해놓는 형식으로 구현 

코드를 직접 확인하는게 더 빠를 것 같음

정답 코드

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

string arr[201];
int r, c, n;
int y_ar[4] = { -1,0,1,0 };
int x_ar[4] = { 0,1,0,-1 };

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> r >> c >> n;
	for (int i = 0; i < r; i++)
		cin >> arr[i];

	if (n % 2 == 0) {
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++)
				cout << 'O';
			cout << "\n";
		}
		return 0;
	}

	string copyed[201];
	for (int i = 0; i < r; i++)
		copyed[i] = arr[i];

	for (int i = 1; i < n; i += 2) {
		for (int j = 0; j < r; j++)
			copyed[j] = arr[j];


		for (int j = 0; j < r; j++)
			for (int k = 0; k < c; k++) 
				if (arr[j][k] == 'O') {
					for (int u = 0; u < 4; u++) {
						int ny = j + y_ar[u];
						int nx = k + x_ar[u];

						if (ny >= 0 && ny < r && nx >= 0 && nx < c)
							copyed[ny][nx] = 'O';
					}
				}

		for (int j = 0; j < r; j++)
			for (int k = 0; k < c; k++) {
				if (copyed[j][k] == 'O')
					arr[j][k] = '.';
				else {
					arr[j][k] = 'O';
				}
			}
	}

	for (int i = 0; i < r; i++)
		cout << arr[i] << "\n";
	

	return 0;
}

문제링크: www.acmicpc.net/problem/20058

삼성 코딩테스트 문제입니다.

구현해야하는 항목이 많아서 번거로운 문제였지만, 구현자체의 난이도는 어려운 문제가 아닙니다.

이런 문제일수록 항목별로 나눠 구현하고 중간중간에 디버깅을 해보면서 정상적으로 동작해야 하는지 확인해야 힙니다.

크게 구현할 내용은

• 1. 입력값 받기
• 2. 구역 범위 나누기
• 3. 90도 회전시키기
• 4. 얼음 녹이기
• 5. 결과값 도출하기

입니다. 

구역 범위는 구획의 크기별로 2중포문을 통해 구현하면 됩니다. 

90도 회전은 temp라는 임시배열을 생성하고 해당 배열에 90도 돌려서 옮겨주면 됩니다. 

이때 모든 부분을 90로 회전하기 때문에 len, y, x 값을 줄이며 반복해줍니다.

얼음 녹이기는 4방향을 비교하며 해결하였고

결과값 도출시에는 bfs를 사용하여 하나의 덩어리합을 구했습니다.

아래는 정답코드입니다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int arr[100][100] = { 0, };
int temp[100][100] = { 0, };
int visited[100][100] = { 0, };

int n, q;
int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };
int result1 = 0, result2 = 0;

void rotate(int sy, int sx, int v) {
	int y = sy;
	int x = sx;
	int len = v;

	while (len > 1) {


		for (int i = y, j = 1; j <= len; j++, i++) {  //1
			temp[y][x + len - j] = arr[i][x];
		}

		for (int i = x, j = 0; j < len; j++, i++) { //2
			temp[y + j][x] = arr[y + len - 1][i];
		}

		for (int i = y + len - 1, j = 0; j < len; j++, i--) {  //3
			temp[y + len - 1][x + j] = arr[i][x + len - 1];
		}


		for (int i = x + len - 1, j = 1; j <= len; j++, i--) { //4
			temp[y + len - j][x + len - 1] = arr[y][i];
		}


		y++;
		x++;
		len -= 2;
	}

}

int bfs(int y, int x, int len) {
	visited[y][x] = 1;
	int result = 1;
	queue <pair <int, int>> que;
	que.push(make_pair(y, x));

	while (!que.empty()) {

		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];

			if (ny >= 1 && ny <= len && nx >= 1 && nx <= len && visited[ny][nx] == 0 && arr[ny][nx] > 0) {
				visited[ny][nx] = 1;
				result++;
				que.push(make_pair(ny, nx));
			}

		}
	}

	return result;

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	//0. input
	cin >> n >> q;
	int len = 1;
	for (int i = 0; i < n; i++)
		len *= 2;
	for (int i = 1; i <= len; i++)
		for (int j = 1; j <= len; j++)
			cin >> arr[i][j];

	for (int k = 0; k < q; k++) {
		int temp1;
		cin >> temp1;
		if (temp1 != 0) { //0이 아닐 때 
			int v = 1;
			for (int i = 0; i < temp1; i++)
				v *= 2;
			//1. divide
			memset(temp, 0, sizeof(temp));
			for (int i = 1; i < len; i += v)
				for (int j = 1; j < len; j += v) {
					//2. rotate
					rotate(i, j, v);
				}
			for (int i = 1; i <= len; i++)
				for (int j = 1; j <= len; j++)
					arr[i][j] = temp[i][j];
		}

		//3. erase ice

		memset(temp, 0, sizeof(temp));

		for (int i = 1; i <= len; i++)
			for (int j = 1; j <= len; j++) {
				temp[i][j] = arr[i][j];
				int zero_ = 0;
				for (int u = 0; u < 4; u++) {
					if (arr[i + y_ar[u]][j + x_ar[u]] != 0)
						zero_++;
				}
				if (zero_ < 3 && arr[i][j] > 0) {
					temp[i][j] --;
				}
			}
		for (int i = 1; i <= len; i++)
			for (int j = 1; j <= len; j++)
				arr[i][j] = temp[i][j];

		/*
		cout << endl;
		for (int i = 1; i <= len; i++) {
		for (int j = 1; j <= len; j++)
		cout << arr[i][j] << ' ';
		cout << endl;
		}*/

	}

	//4. result

	for (int i = 1; i <= len; i++)
		for (int j = 1; j <= len; j++) {
			result1 += arr[i][j];
			if (visited[i][j] == 0 && arr[i][j] > 0)
				result2 = max(result2, bfs(i, j, len));
		}



	cout << result1 << endl;
	cout << result2 << endl;
}

문제링크:www.acmicpc.net/problem/20057

20년도 하반기 삼성 코딩테스트 기출문제입니다.

저는 오전에 풀어서 접하지 못했던 문제입니다. 

우선 크게 구현해야하는 부분이 4가지 였습니다.

• 1. 입력 받기
• 2. 회전시키기
• 3. 모래 이동
• 4. 결과 도출

2, 3번이 핵심입니다.

우선 회전은 for문과 y_ar, x_ar(방향배열)을 통해서 구현했습니다.

가운데 점부터 시작하여 방향별로 cnt 갯수만큼 점을 옮겨줌으로서 2번 회전을 구현했습니다.

그렇다면 3번 모래 이동은 어떤식으로 구현할까요?

저는 구조체를 하나 생성했습니다.

typedef struct a {
	vector <int> vec;
	double per;

}moved;

해당 구조체에 vec에는 모래가 이동하는 좌표로 가기위해 필요 값들을 그리고 per에는 해당 좌표에 대한 퍼센트를 기입해놓았습니다. 현재 방향에 따라서 값을 더해주는 형태로 구현했기 때문에 아래처럼 간단하게 구현할 수 있었습니다.

아래는 정답코드입니다. 해당 문제에서 주의할 점은 수의 범위가 넘어갈 때에는 예외처리를 통해서 데이터를 지우게끔 해야하는 것입니다. 

#include <iostream>
#include <vector>
using namespace std;

typedef struct a {
	vector <int> vec;
	double per;

}moved;

int n = 0, result =0;
int arr[501][501] = { 0, };
moved val[9];
int y_ar[4] = { 0,1,0,-1 };
int x_ar[4] = { -1,0,1,0 };

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//init
	val[0].vec.push_back(1), val[0].per = 0.01;
	val[1].vec.push_back(3), val[1].per = 0.01;
	val[2].vec.push_back(1), val[2].vec.push_back(0), val[2].per = 0.07;
	val[3].vec.push_back(3), val[3].vec.push_back(0), val[3].per = 0.07;
	val[4].vec.push_back(1), val[4].vec.push_back(1), val[4].vec.push_back(0), val[4].per = 0.02;
	val[5].vec.push_back(3), val[5].vec.push_back(3), val[5].vec.push_back(0), val[5].per = 0.02;
	val[6].vec.push_back(1), val[6].vec.push_back(0), val[6].vec.push_back(0), val[6].per = 0.1;
	val[7].vec.push_back(3), val[7].vec.push_back(0), val[7].vec.push_back(0), val[7].per = 0.1;
	val[8].vec.push_back(0), val[8].vec.push_back(0), val[8].vec.push_back(0), val[8].per = 0.05;
	//0.
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
			result += arr[i][j];
		}
	
	//1. rotate
	int cy = n / 2 + 1, cx = n / 2 + 1, dir = 0, cnt = 0;
	for (int k = 0; k < n * 2 - 1; k++) {
		if (k % 2 == 0)
			cnt++;
		for (int i = 0; i < cnt; i++) { // 해당방향으로 이동
			int curval = arr[cy + y_ar[dir]][cx + x_ar[dir]];

			for (int j = 0; j < 9; j++) {
				int ny = cy;
				int nx = cx;
				for (int u = 0; u < val[j].vec.size(); u++) {
					ny += y_ar[(dir + val[j].vec[u]) % 4];
					nx += x_ar[(dir + val[j].vec[u]) % 4];
				}
				if (ny >= 1 && ny <= n && nx >= 1 && nx <= n) {
					arr[ny][nx] += (int)(curval * val[j].per);
				}
				arr[cy + y_ar[dir]][cx + x_ar[dir]] -= (int)(curval * val[j].per);

			}
			//알파 계산 
			if (cy + y_ar[dir] * 2 >= 1 && cy + y_ar[dir] * 2 <= n && cx + x_ar[dir] * 2 >= 1 && cx + x_ar[dir] * 2 <= n) 
				arr[cy + y_ar[dir] * 2][cx + x_ar[dir] * 2] += arr[cy + y_ar[dir]][cx + x_ar[dir]];
			
			if(cy + y_ar[dir] >= 1 && cy + y_ar[dir] <= n && cx + x_ar[dir] >= 1 && cx + x_ar[dir] <= n)
				arr[cy + y_ar[dir]][cx + x_ar[dir]] = 0;

			cy += y_ar[dir], cx += x_ar[dir]; // 실제 좌표 이동

			/*
			cout << endl;
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++)
					cout << arr[i][j] << ' ';
				cout << endl;
			}*/
		}
		
		dir++;
		if (dir == 4)
			dir = 0;

		
	}





	int sum = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) 
			sum += arr[i][j];	
	result -= sum;
	cout << result << endl;
	return 0;
}

문제링크:www.acmicpc.net/problem/20055

20년도 하반기 삼성 코딩테스트 기출문제입니다.

저는 실제 코딩테스트로 먼저 접했던 문제입니다.

문제는 거의 비슷하고, 코딩테스트에서는 더 자세하게 설명해줍니다.

해야하는 일들을 순서대로 구현하면 되는 시뮬레이션 문제입니다.

1. 벨트가 한 칸 회전한다.
2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
   1. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
3. 올라가는 위치에 로봇이 없다면 로봇을 하나 올린다.
4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.

4가지를 반복하며 결과를 도출하면 됩니다.

저는 dequeue 를 사용하지 않고 단순 배열을 이용해서 구현했습니다.

#include <iostream>
#include <vector>
using namespace std;

int n = 0, k = 0;
int arr[201][2] = { 0, };
int cnt = 1;
vector <int> vec;


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);


	//0.
	cin >> n >> k;
	for (int i = 1; i <= 2 * n; i++)
		cin >> arr[i][0];

	while (1) {
		//1.
		int temp = arr[2 * n][0];
		int temp2 = arr[2 * n][1];

		if (arr[n][1] == 1) { // 나갈친구 미리 제거
			arr[n][1] = 0;
		}
		for (int i = 2 * n; i > 1; i--) {
			arr[i][0] = arr[i - 1][0];
			arr[i][1] = arr[i - 1][1];
		}
		arr[1][0] = temp;
		arr[1][1] = temp2;
		
		//로봇도 이동시켜줘야지
		for (int i = 0; i < vec.size(); i++) {
			if (vec[i] < n)
				vec[i]++;
			else if (vec[i] == n) {
				//arr[vec[i] + 1][1] = 0;
				vec.erase(vec.begin() + i);
				i--;
			}
		}


		//2. 
		for (int i = 0; i < vec.size(); i++) {
			int x = vec[i];
			if (x < n && arr[x + 1][0] > 0 && arr[x + 1][1] == 0) {
				
				arr[x + 1][0]--;
				arr[x + 1][1] = 1; //로봇이 있다.// 로봇이 있음 1 없음 0 
				arr[x][1] = 0; // 이제 없다. 
				vec[i]++;
			}
			else if (x == n) {
				arr[x][1] = 0;
				vec.erase(vec.begin() + i);
				i--;
			}
		}

		//3.
		if (arr[1][1] == 0 && arr[1][0] > 0) {
			arr[1][0]--;
			arr[1][1] = 1;
			vec.push_back(1);
		}
		//4. 
		int v = 0;
		for (int i = 1; i <= 2 * n; i++) {
			if (arr[i][0] == 0)
				v++;
		}
		if (v >= k) {
			cout << cnt << endl;
			return 0;
		}
		cnt++;



	}



	return 0;
}

문제링크:www.acmicpc.net/problem/8911

간단한 시뮬레이션 문제입니다.

이동방향에 따라 이동시켜주면서 max y, x 값과 min y,x값을 찾아주면 되는 문제입니다.

이동할때는 4방향 배열을 사용해서 문제를 해결합니다.

바로 정답코드입니다.

#include <iostream>
#include <string>
#include <cmath>
using namespace std;


int t = 0;
int y_arr[4] = { -1,0,1,0 }; //북 동 남 서 방향
int x_arr[4] = { 0,1,0,-1 };

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> t;

	while (t--) {
		int cy = 0, cx = 0, dir = 0;
		int minx = 0, miny = 0, maxx = 0, maxy = 0;

		string arr;
		cin >> arr;

		for (int i = 0; i < arr.size(); i++) {
			int ny, nx;
			if (arr[i] == 'F') {
				cy = y_arr[dir%4] + cy;
				cx = x_arr[dir%4] + cx;
			}
			else if (arr[i] == 'B') {
				cy = y_arr[(dir+2)%4] + cy;
				cx = x_arr[(dir+2)%4] + cx;
			}
			else if (arr[i] == 'R') {
				dir++;
			}
			else if (arr[i] == 'L') {
				dir--;
				if (dir < 0)
					dir += 4;
			}

		//	cout << i + 1<<"x y" << cx << ' ' << cy <<" dir "<<dir<<endl;
			if (maxx < cx)
				maxx = cx;
			if (maxy < cy)
				maxy = cy;
			if (minx > cx)
				minx = cx;
			if (miny > cy)
				miny = cy;
		}
		//cout << maxy << ' ' << maxx << ' ' << miny << ' ' << minx << endl;
		cout << ((maxy - miny)* (maxx - minx)) << "\n";

	}


	return 0;
}

문제링크:www.acmicpc.net/problem/19236

삼성 코딩테스트에서 나온 청소년 상어입니다. 

기존 아기상어는 쉽게 접근했는데 청소년상어는 애먹었습니다.

우선 크게 

1. 물고기의 이동

2. 상어의 이동 

으로 구분할 수 있습니다.

물고기는 이동이 불가할 경우 반시계방향으로 방향을 방향을 바꾸게 됩니다. 

그렇기 때문에 첫번째 이동과 두번째 이상부터의 이동을 구분해주어야 합니다. (방향을 다르게 설정해주기 때문에)

아래가 물고기 이동의 코드입니다.

	// fish
	for (int i = 1; i <= 16; i++) {
		if (fishes[i].alive== false)
			continue;
		int y = fishes[i].y;
		int x = fishes[i].x;
		int dir = fishes[i].dir;

		int ny = y + y_ar[dir];
		int nx = x + x_ar[dir];
		bool jud = false;

		if (ny >= 0 && ny < 4 && nx >= 0 && nx < 4) {
			if (arr[ny][nx] == 0) { //없으면

				jud = true;
				fishes[i].y = ny;
				fishes[i].x = nx;
				arr[ny][nx] = i;
				arr[y][x] = 0;
				
			}
			else if (arr[ny][nx] != -1) {// 물고기가 있으면
				jud = true;
			
				fish temp = fishes[i];
				fishes[i].y = fishes[arr[ny][nx]].y;	
				fishes[i].x = fishes[arr[ny][nx]].x;
				fishes[arr[ny][nx]].y = temp.y;
				fishes[arr[ny][nx]].x = temp.x;

				int temp2;
				temp2 = arr[y][x];
				arr[y][x] = arr[ny][nx];
				arr[ny][nx] = temp2;

			}


		}
		if (jud == true) continue;
		else {
			int ndir = dir + 1;
			if (ndir == 9) ndir = 1;
			int ny = y + y_ar[ndir];
			int nx = x + x_ar[ndir];


			while (ndir != dir) {
				if (ny >= 0 && ny < 4 && nx >= 0 && nx < 4) {
					if (arr[ny][nx] == 0) { //없으면

						
						fishes[i].y = ny;
						fishes[i].x = nx;
						fishes[i].dir = ndir;
						arr[ny][nx] = i;
						arr[y][x] = 0;

						break;
					}
					else if (arr[ny][nx] != -1) {// 물고기가 있으면
						
						fish temp = fishes[i];
						fishes[i].y = fishes[arr[ny][nx]].y;
						fishes[i].x = fishes[arr[ny][nx]].x;
						fishes[arr[ny][nx]].y = temp.y;
						fishes[arr[ny][nx]].x = temp.x;
						

						int temp2;
						temp2 = arr[y][x];
						arr[y][x] = arr[ny][nx];
						arr[ny][nx] = temp2;

						fishes[i].dir = ndir;
						break;

					}

				}
				ndir++;
				if (ndir == 9) ndir = 1;
				ny = y + y_ar[ndir];
				nx = x + x_ar[ndir];

			}
		}



	}

이후 상어의 이동은 dfs로 구현하고 갈 수 있는 모든 경우를 고려해줍니다.

	// 상어의 이동
	//1. 해당 방향으로 이동 (가능한 경우 모두)	
	
	int nx = shark.x;
	int ny = shark.y;

	while (1) {

		ny += y_ar[shark.dir];
		nx += x_ar[shark.dir];

		if (ny >= 0 && ny < 4 && nx >= 0 && nx < 4) {


			//1. 상어의 위치 바꾸기 2. 그 위치에 물고기
			if (arr[ny][nx] == 0) continue;


			int fishnum = arr[ny][nx];
			int ndir = fishes[fishnum].dir;

			arr[shark.y][shark.x] = 0;
			arr[ny][nx] = -1;
			shark = fishes[fishnum];
			fishes[fishnum].alive = false;


			dfs(fishes, shark, arr, cnt + fishnum);

			fishes[fishnum].alive = true;
			arr[ny][nx] = fishnum;
			shark = b;
			arr[shark.y][shark.x] = -1;


		}
		else
			break;

	}

두가지를 반복하며 결과를 추론해갑니다.

꼼꼼하게 조건을 따져보고 미리 설계를 정확하게 해야 쉽게 풀 수있습니다.

그리고 물고기 이동 후 미리 결과를 돌려보며 정확하게 행동하는지도 비교해야 합니다.

정답코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;

typedef struct {
	int y, x;
	int dir;
	bool alive;
}fish;

int result = 0;
int y_ar[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
int x_ar[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
bool ended = false;


void dfs(fish a[17], fish b, int c[4][4],int cnt) {
	
	result = max(result, cnt);

	fish fishes[17];
	fish shark;
	int arr[4][4];

	for (int i = 1; i <= 16; i++)
		fishes[i] = a[i];
	shark = b;
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			arr[i][j] = c[i][j];




	// fish
	for (int i = 1; i <= 16; i++) {
		if (fishes[i].alive== false)
			continue;
		int y = fishes[i].y;
		int x = fishes[i].x;
		int dir = fishes[i].dir;

		int ny = y + y_ar[dir];
		int nx = x + x_ar[dir];
		bool jud = false;

		if (ny >= 0 && ny < 4 && nx >= 0 && nx < 4) {
			if (arr[ny][nx] == 0) { //없으면

				jud = true;
				fishes[i].y = ny;
				fishes[i].x = nx;
				arr[ny][nx] = i;
				arr[y][x] = 0;
				
			}
			else if (arr[ny][nx] != -1) {// 물고기가 있으면
				jud = true;
			
				fish temp = fishes[i];
				fishes[i].y = fishes[arr[ny][nx]].y;	
				fishes[i].x = fishes[arr[ny][nx]].x;
				fishes[arr[ny][nx]].y = temp.y;
				fishes[arr[ny][nx]].x = temp.x;

				int temp2;
				temp2 = arr[y][x];
				arr[y][x] = arr[ny][nx];
				arr[ny][nx] = temp2;

			}


		}
		if (jud == true) continue;
		else {
			int ndir = dir + 1;
			if (ndir == 9) ndir = 1;
			int ny = y + y_ar[ndir];
			int nx = x + x_ar[ndir];


			while (ndir != dir) {
				if (ny >= 0 && ny < 4 && nx >= 0 && nx < 4) {
					if (arr[ny][nx] == 0) { //없으면

						
						fishes[i].y = ny;
						fishes[i].x = nx;
						fishes[i].dir = ndir;
						arr[ny][nx] = i;
						arr[y][x] = 0;

						break;
					}
					else if (arr[ny][nx] != -1) {// 물고기가 있으면
						
						fish temp = fishes[i];
						fishes[i].y = fishes[arr[ny][nx]].y;
						fishes[i].x = fishes[arr[ny][nx]].x;
						fishes[arr[ny][nx]].y = temp.y;
						fishes[arr[ny][nx]].x = temp.x;
						

						int temp2;
						temp2 = arr[y][x];
						arr[y][x] = arr[ny][nx];
						arr[ny][nx] = temp2;

						fishes[i].dir = ndir;
						break;

					}

				}
				ndir++;
				if (ndir == 9) ndir = 1;
				ny = y + y_ar[ndir];
				nx = x + x_ar[ndir];

			}
		}



	}



	// 상어의 이동
	//1. 해당 방향으로 이동 (가능한 경우 모두)	
	
	int nx = shark.x;
	int ny = shark.y;

	while (1) {

		ny += y_ar[shark.dir];
		nx += x_ar[shark.dir];

		if (ny >= 0 && ny < 4 && nx >= 0 && nx < 4) {


			//1. 상어의 위치 바꾸기 2. 그 위치에 물고기
			if (arr[ny][nx] == 0) continue;


			int fishnum = arr[ny][nx];
			int ndir = fishes[fishnum].dir;

			arr[shark.y][shark.x] = 0;
			arr[ny][nx] = -1;
			shark = fishes[fishnum];
			fishes[fishnum].alive = false;


			dfs(fishes, shark, arr, cnt + fishnum);

			fishes[fishnum].alive = true;
			arr[ny][nx] = fishnum;
			shark = b;
			arr[shark.y][shark.x] = -1;


		}
		else
			break;

	}



}

int main() {
	int a, b;

	fish fishes[17];
	fish shark;
	int arr[4][4];
	int fishnum;

	for(int i=0;i<4;i++)
		for (int j = 0; j < 4; j++) {
			cin >> a >> b;
			if (i == 0 && j == 0) {
				shark = { i,j,b,1 };
				fishes[a] = { 0,0,0,0 };
				arr[0][0] = -1;
				fishnum = a;
				continue;
			}
			else{
				fishes[a] = { i,j,b,1 };
				arr[i][j] = a;
				}
		}



	dfs(fishes, shark, arr, fishnum);

	cout << result << endl;

}

문제링크:https://www.acmicpc.net/problem/13460

이 문제는 13459번 구슬 탈출과 동일한 문제입니다. 다만 이동 경로값을 출력해주어야 하기 때문에 기존에 bfs를 사용하는게 편하다는 점이 있습니다. 

1. bfs와 while문을 사용하여 행동을 구현한다.

    - 이동할 곳이 #이 아니고 현재있는 좌표가 O가 아니면 계속 이동하게끔 구현한다.

2.이동후 두좌표가 같을때를 확인해준다.

    - 경우는 2가지이다. 함께 O에 있을때, 한쪽 끝에 함께 몰려있을때  함께 O라면 실패이기 때문에 큐에 넣지않고 마무       리 한쪽 끝이라면 값을 비교해서 하나를 한칸뒤로 무른다. 

3. 매 반복마다 result값을 증가시킨다. (구슬 탈출2 에서 유효)

정답코드입니다.

#include <iostream>
#include <queue>
#include <math.h>
using namespace std;

int n = 0, m = 0;
char arr[11][11];
bool visited[11][11][11][11] = { 0, };
int result = 0;

int ry, rx, by, bx;
int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };


int bfs() {
	queue <pair<int, int>> red_que;
	queue <pair<int, int>> blue_que;
	red_que.push(make_pair(ry, rx));
	blue_que.push(make_pair(by, bx));
	visited[ry][rx][by][bx] = 1;
	

	while (!red_que.empty()) {
		int sized = red_que.size();



		while (sized--) {

			int red_cy = red_que.front().first;
			int red_cx = red_que.front().second;
			int blue_cy = blue_que.front().first;
			int blue_cx = blue_que.front().second;


			red_que.pop(), blue_que.pop();

			if (arr[red_cy][red_cx] == 'O')
				return result;

			for (int i = 0; i < 4; i++) {
				int red_ny = red_cy;
				int red_nx = red_cx;
				int blue_ny = blue_cy;
				int blue_nx = blue_cx;

				while (arr[red_ny + y_ar[i]][red_nx + x_ar[i]] != '#' && arr[red_ny][red_nx] != 'O') {
					red_ny += y_ar[i];
					red_nx += x_ar[i];

				}
				while (arr[blue_ny + y_ar[i]][blue_nx + x_ar[i]] != '#' && arr[blue_ny][blue_nx] != 'O') {
					blue_ny += y_ar[i];
					blue_nx += x_ar[i];
				}

				if (red_ny == blue_ny && red_nx == blue_nx) {

					if (arr[red_ny][red_nx] == 'O') continue; // 할 필요가 없지

					if ((abs(red_ny - red_cy) + abs(red_nx - red_cx)) > (abs(blue_ny - blue_cy) + abs(blue_nx - blue_cx)))
						red_ny -= y_ar[i], red_nx -= x_ar[i];
					else
						blue_ny -= y_ar[i], blue_nx -= x_ar[i];
				}

				if (visited[red_ny][red_nx][blue_ny][blue_nx]) continue;

				red_que.push(make_pair(red_ny, red_nx));
				blue_que.push(make_pair(blue_ny, blue_nx));
				visited[red_ny][red_nx][blue_ny][blue_nx] = 1;

			}

		}

		if (result == 10)
			return -1;
		result++;

	}

	return -1;

}


int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'R')
				ry = i, rx = j, arr[i][j] = '.';
			else if (arr[i][j] == 'B')
				by = i, bx = j, arr[i][j] = '.';
		}

	cout << bfs() << endl;

	return 0;
}