이것 저것 &

문제링크: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/1261

bfs문제인데 조금 꼬아놓은 bfs였습니다! 

최단 경로이동이 아니라 벽을 최소로 부수며 이동할때의 벽을 최소 몇 개 부수어야 하는지이기 때문에 방문 배열이 총 2개가 필요합니다.

1. 방문했는지 여부를 판단해주는 배열

2. 방문했다면 해당 경로로 최소 몇번만에 도달할 수 있는 표시하는 배열

쉬운문제였기 때문에 바로 정답코드입니다.

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

int m, n;
int arr[101][101] = { 0, };
int visited[101][101][2] = { 0, };

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

void bfs() {

	queue <pair<int, int>> que;
	que.push(make_pair(1, 1));
	if (arr[1][1] == 1) visited[1][1][0] = 1, visited[1][1][1] = 1;
	else visited[1][1][0] = 1, visited[1][1][1] = 0;

	while (!que.empty()) {

		int yy = que.front().first;
		int xx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int y = yy + y_ar[i];
			int x = xx + x_ar[i];

			if (y >= 1 && y <= n && x >= 1 && x <= m) {
				if (visited[y][x][0] == 0) { //방문한적 없어
					visited[y][x][0] = 1, visited[y][x][1] = visited[yy][xx][1] + arr[y][x];
					que.push(make_pair(y, x));	
				}
				else { // 방문했다면, 
					if (visited[y][x][1] > (visited[yy][xx][1] + arr[y][x])) { 
						visited[y][x][0] = 1, visited[y][x][1] = visited[yy][xx][1] + arr[y][x];
						que.push(make_pair(y, x));
					}
					

				}
			}

		}

	}

}

int main() {
	cin >> m >> n;
	for (int i = 1; i <= n; i++){
			string temp;
			cin >> temp;
			for (int j = 1; j <= m; j++)
				arr[i][j] = temp.at(j - 1) - '0';
	}

	
	bfs();

	
	cout << visited[n][m][1] << "\n";
}

 visited[yy][xx][1] + arr[y][x]는 지금까지 벽을 부순횟수 더하기 현재 벽이 있다면 부수고 들어가고(+1) 아니면(+0)을 하는 코드입니다. 

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

일반적인 방법으로 풀면은 시간초과입니다.

dfs를 사용하고 이미 확인한 값에 대해서는 탐색하지 않는 백트래킹 기법을 사용해야 하는 어려운 문제였습니다.

이문제에서의 핵심은

bool row[9][10] = { 0 };
bool col[9][10] = { 0 };
bool square[9][10] = { 0 };

 세가지 방문여부입니다. row는 해당 행에서 수를 탐색했는지 여부, col은 열에서 수를 탐색했는지 여부, square는 속하는 3x3에서 수를 탐색했는지 여부를 판단합니다.

int main() {

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

	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++) {
			cin >> arr[i][j];



			if (arr[i][j] != 0)
			{
				row[i][arr[i][j]] = true;
				col[j][arr[i][j]] = true;
				square[(i / 3) * 3 + (j / 3)][arr[i][j]] = true;
			}


		}

	dfs(0);



}

위 처럼 수를 입력받으면 row, col, square에 방문 수를 저장합니다. 

row[i][j] 라면 i행에서 j값을 방문했는지 여부를 표시합니다 즉 row[1][9]= true 면은 1행에 9는 존재한다는 의미입니다.

col과 square 모두 같은 맥락입니다.

이때 스퀘어는 

위와 같은 구조로 진행됩니다. (출처: 얍문님 티스토리)  

그렇기 때문에 (y/3)*3 + x/3 을 통해서 해당 위치에 표시하는 것입니다.

정답코드입니다. cnt값을 올려주며 진행하게 됩니다. 81일때에는 모든 값들이 채워져 있는 것이기에 종료하게 됩니다.

이때 exit(0)를 이용해서 바로 프로세스를 종료해버리면 시간을 단축시킵니다. 천천히 이해해보세요.

#include <iostream>
#include <cstring>
#include <stdlib.h>
using namespace std;

int arr[9][9] = { 0 };
bool row[9][10] = { 0 };
bool col[9][10] = { 0 };
bool square[9][10] = { 0 };




void dfs(int cnt) {

	if (cnt == 81) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)
				cout << arr[i][j] << ' ';
			cout << endl;
		}
		exit(0);
	}
	int y = cnt / 9;
	int x = cnt % 9;

	if (arr[y][x] != 0)
		dfs(cnt + 1);
	else {
		
		for (int i = 1; i <= 9; i++) {
			if (row[y][i] == 0 && col[x][i] == 0 && square[(y / 3) * 3 + (x / 3)][i] == 0) {
				row[y][i] = 1;
				col[x][i] = 1;
				square[(y / 3) * 3 + (x / 3)][i] = 1;

				arr[y][x] = i;
				dfs(cnt + 1);
				arr[y][x] = 0;

				row[y][i] = 0;
				col[x][i] = 0;
				square[(y / 3) * 3 + (x / 3)][i] = 0;

			}

		}

	}


	return;
	
}


int main() {

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

	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++) {
			cin >> arr[i][j];



			if (arr[i][j] != 0)
			{
				row[i][arr[i][j]] = true;
				col[j][arr[i][j]] = true;
				square[(i / 3) * 3 + (j / 3)][arr[i][j]] = true;
			}


		}

	dfs(0);



}

문제링크: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;
}

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

까다로운 문제였습니다. 10번까지 검증하기 때문에 dfs가 아니라 bfs로 구현해야 했습니다.

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

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

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

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

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

정답코드입니다.

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

int n = 0, m = 0;
char arr[12][12];

int r_y, r_x;
int b_y, b_x;
int result = 0;

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

int bfs() {

	queue <pair <int, int>> b_que;
	queue <pair <int, int>> r_que;
	b_que.push(make_pair(b_y, b_x));
	r_que.push(make_pair(r_y, r_x));

	result = 0; // 0으로 초기화
	while (!b_que.empty()) {
		int sized = b_que.size();

		while (sized--) {
			int red_y = r_que.front().first;
			int red_x = r_que.front().second;
			int blue_y = b_que.front().first;
			int blue_x = b_que.front().second;
			r_que.pop(), b_que.pop();


			if (arr[red_y][red_x] == 'O') // O에 있을때
				return result;
			
			for (int i = 0; i < 4; i++) {
				int nextred_y = red_y;
				int nextred_x = red_x;
				int nextblue_y = blue_y;
				int nextblue_x = blue_x;

				while (arr[nextred_y + y_ar[i]][nextred_x + x_ar[i]] != '#' && arr[nextred_y][nextred_x] != 'O') {
					nextred_y += y_ar[i];
					nextred_x += x_ar[i];
				}
				while (arr[nextblue_y + y_ar[i]][nextblue_x + x_ar[i]] != '#' && arr[nextblue_y][nextblue_x] != 'O') {
					nextblue_y += y_ar[i];
					nextblue_x += x_ar[i];
				}
				if (nextred_y == nextblue_y && nextred_x == nextblue_x) {
					if (arr[nextred_y][nextred_x] == 'O') continue; // 이 경로는 가면 안되는 경로라서 continue로 넘겨줌 	

					// 더 많이 이동한쪽이 진짜 자기 위치  
					if ((abs(nextred_y - red_y) + abs(nextred_x - red_x)) > (abs(nextblue_y - blue_y) + abs(nextblue_x - blue_x)))
						nextred_y -= y_ar[i], nextred_x -= x_ar[i];
					else
						nextblue_y -= y_ar[i], nextblue_x -= x_ar[i];
						
				}

				if (visited[nextred_y][nextred_x][nextblue_y][nextblue_x]) continue; //기존에 방문했다면 
				r_que.push(make_pair(nextred_y,nextred_x));
				b_que.push(make_pair(nextblue_y,nextblue_x));
				visited[nextred_y][nextred_x][nextblue_y][nextblue_x] = 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] == 'B')
				b_y = i, b_x = j, arr[i][j] = '.';
			else if (arr[i][j] == 'R')
				r_y = i, r_x = j, arr[i][j] = '.';
		}


	if (bfs() == -1)
		cout << 0 << endl;
	else
		cout << 1 << endl;


	
	return 0;
}

스스로 부족한 것을 많이 느꼈습니다. 구슬탈출2를 풀어보면서 더욱 연습할 계획입니다. 

아래는 dfs를 통해 구현한 코드입니다.

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

int n, m;
string arr[10];
bool result = 0;
int y_ar[4] = { 0,1,0,-1 };
int x_ar[4] = { -1,0,1,0 };

void dfs(int cnt, int ry, int rx, int by, int bx) {
	if (cnt == 10)
		return;
	if (result)
		return;

	for (int i = 0; i < 4; i++) {

		int nry = ry, nrx = rx;
		int nby = by, nbx = bx;
		bool blue = false, red = false;
		while (1) {

			if (arr[nry + y_ar[i]][nrx + x_ar[i]] == '.') {
				nry += y_ar[i];
				nrx += x_ar[i];
			}
			else if (arr[nry + y_ar[i]][nrx + x_ar[i]] == 'O') {
				nry += y_ar[i];
				nrx += x_ar[i];
				red = true;
				break;
			}
			else if (arr[nry + y_ar[i]][nrx + x_ar[i]] == '#') {
				break;
			}
		}

		while (1) {
			if (arr[nby + y_ar[i]][nbx + x_ar[i]] == '.') {
				nby += y_ar[i];
				nbx += x_ar[i];
			}
			else if (arr[nby + y_ar[i]][nbx + x_ar[i]] == 'O') {
				nby += y_ar[i];
				nbx += x_ar[i];
				blue = true;
				break;
			}
			else if (arr[nby + y_ar[i]][nbx + x_ar[i]] == '#') {
				break;
			}
		}

		if (blue == true)
			continue;
		if (red == true) {
			result = true;
			return;
		}

		if (nrx == nbx && nry == nby) {			//포개진 경우
			if (i == 0) {
				if (rx > bx) 	nrx += 1;	//빨간공이 밑에 있었던 경우
				else			nbx += 1;
			}
			else if (i == 1) {
				if (ry > by)	nby -= 1;		//파란공이 더 왼쪽에서 시작한 경우
				else			nry -= 1;
			}
			else if (i == 2) {
				if (rx > bx)		nbx -= 1;		//파란공이 더 위에서 시작
				else				nrx -= 1;
			}
			else if (i == 3) {
				if (ry > by)		nry += 1;		//빨간공이 더 오른쪽에서 시작
				else				nby += 1;
			}
		}

		dfs(cnt + 1, nry, nrx, nby, nbx);




	}

}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;

	int ry, rx, by, bx;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		for (int j = 0; j < m; 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] = '.';
			}
		}
	}

	dfs(0, ry, rx, by, bx);
	cout << result << endl;

	return 0;
}

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

전형적인 브루트포스 문제입니다.

 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 

이라는 조건이 있기 때문에 모든 경우의 수를 대입해서 결과를 유추할 수 있기 때문입니다.

저는 크게 두가지 기능으로 분류했습니다.

1. 경로를 선택하는 함수 SELECTED 

2. 해당 사다리가 올바르게 i번 세로선의 결과가 i번이 나오는지 확인하는 함수 JUDMENT

2번 함수 같은 경우에는 쉽게 구현이 가능합니다.

bool judment() {


	for (int i = 1; i <= n; i++) { //세로 

		int ii = i; //열

		for (int j = 1; j <= h; j++) {
			if (arr[j][ii] == 1)
				ii++;
			else if (arr[j][ii - 1] == 1) {
				ii--;
			}
		}

		if (ii != i)
			return false;
	}

	return true;
}

1번 함수같은 경우에는 조금 해맸는데, DFS를 사용해서 구현하였습니다.

void selected(int y, int cnt) {
	if (flag == true)
		return;

	if (cnt == leadercnt) {
		flag = judment();

		return;
	}

	for (int i = y; i <= h; i++) {
		for (int j = 1; j < n; j++) {
			if (arr[i][j] == 0 && arr[i][j - 1] == 0 && arr[i][j + 1] == 0)
			{

				arr[i][j] = 1;
				selected(i, cnt + 1);
				arr[i][j] = 0;
			}

		}
	}

	return;
}

FLAG값이 참이거나 원하는 CNT값과 같거나 큰 경우에는 더 진행할 필요가 없기때문에 RETURN;을 통해서 함수를 종료하였습니다. 그리고 매개변수 Y을 사용하여서 기존에 검사했던 좌표들을 중복으로 검사하지 않게끔 구현하였습니다. 

정답코드입니다.

/*
1. 선택하는 함수  selected
경로를 선택, visited에 쓰고 다시 지우고 판단함수 호출
2. 판단하는 함수  judment
반복문을 돌며 올바르게 동작하면 cnt값을 전달하게 끔
*/
#include <iostream>
using namespace std;

int n = 0, m = 0, h = 0;
bool arr[32][12] = { 0 };
int cnt = 0;
int leadercnt;


bool flag;

bool judment() {


	for (int i = 1; i <= n; i++) { //세로 

		int ii = i; //열

		for (int j = 1; j <= h; j++) {
			if (arr[j][ii] == 1)
				ii++;
			else if (arr[j][ii - 1] == 1) {
				ii--;
			}
		}

		if (ii != i)
			return false;
	}

	return true;
}


void selected(int y, int cnt) {
	if (flag == true)
		return;

	if (cnt == leadercnt) {
		flag = judment();

		return;
	}

	for (int i = y; i <= h; i++) {
		for (int j = 1; j < n; j++) {
			if (arr[i][j] == 0 && arr[i][j - 1] == 0 && arr[i][j + 1] == 0)
			{

				arr[i][j] = 1;
				selected(i, cnt + 1);
				arr[i][j] = 0;
			}

		}
	}

	return;
}




int main() {
	

	int a = 0, b = 0;

	cin >> n >> m >> h;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		arr[a][b] = 1;
	}

	for (int i = 0; i <= 3; i++) {
		flag = false;
		leadercnt = i;
		selected(1, 0);

		if (flag == true) {
			cout << i << "\n";
			return 0;
		}
	}

	cout << -1 << "\n";
	return 0;

}

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

시뮬레이션 문제입니다.

아래 조건들을 만족시키며 진행해야 합니다. 

/*
국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
연합을 해체하고, 모든 국경선을 닫는다.
*/

알고리즘 입니다.

• 반복문을 통해서 각점들에서 dfs(혹은 bfs)를 통해서 인구이동이 가능한지 확인   
  - visited 사용(방문여부), sum(배열값 합), cnt 사용(배열 개수), vetor(방문 배열 좌표)
• dfs(혹은 bfs)후에 변경된 값들을 arr에 저장, 이때 cnt는 2보다 크거나 같아야한다.  bool값도 변경한다.
• bool값을 확인하고 반복문을 break할지 카운트값(result)을 올릴지 판단한다.

정답코드입니다.

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

int arr[51][51] = { 0 };
bool visited[51][51];

int n = 0, l = 0, r = 0;
int result = 0; 
int cnt, sum;
vector <pair <int, int>> vec;

//dfs 방향
int y_ar[4] = { 1,-1,0,0 };
int x_ar[4] = { 0,0,1,-1 };

void dfs(int yy, int xx) {

	for (int i = 0; i < 4; i++) {
		int y = yy + y_ar[i];
		int x = xx + x_ar[i];

		if (!visited[y][x]) {
			if (y >= 0 && y < n&&x >= 0 && x < n) {
				if (abs(arr[yy][xx] - arr[y][x]) >= l && abs(arr[yy][xx] - arr[y][x]) <= r) {
					visited[y][x] = 1;
					cnt++;
					sum += arr[y][x];
					vec.push_back(make_pair(y, x));
					dfs(y, x);
				}
			}
		}
	}
}


int main() {
	cin >> n >> l >> r;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> arr[i][j];

	while (1) {
		bool jud = false;
		memset(visited, 0, sizeof(visited));

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

					vec.clear();
					cnt = 1;
					sum = arr[i][j];
					visited[i][j] = 1;

					vec.push_back(make_pair(i,j));
					dfs(i, j);
					
					if (cnt >= 2) {
						jud = true;
						int aver_val = sum / cnt;
						for (int k = 0; k < vec.size(); k++) 
							arr[vec.at(k).first][vec.at(k).second] = aver_val;
						
					}

				}
			}
		}


		if (jud == false)
			break;
		else
			result++;


	}
	cout << result << endl;
}

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

BFS를 사용하여 해결하는 문제였습니다. 

수의 범위가 0 이상 10,000 미만의 십진수이기 때문에 visited 배열을 만들어서 방문 했던 값을 표시하면서 시간을 확보 했습니다. queue를 pair로 사용해서 int, string 함께 저장하여 해결하였습니다. 

string을 쓰지않고 char형 만으로 구현하는게 베스트인 문제입니다! (사실 string을 사용하면 시간초과가 나게끔 유도한 느낌의 문제였습니다.. ㅠㅠ) 

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

int t = 0;
int a = 0, b = 0;
bool visited[10000];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> t;

	string result;

	while (t--) {
		memset(visited, 0, sizeof(visited));

		result = "";

		cin >> a >> b;
		queue <pair<int, string>> que;
		// 0 -> D 1 -> S 2 -> L 3 -> R
		que.push(make_pair(a, ""));
		visited[a] = 1;
		string word;
		while (!que.empty()) {

			int num = que.front().first;
			word = que.front().second;
			que.pop();
			
			if (num == b) {
				result = word;
				break;
			}

			int verifed_num = (num * 2) % 10000;
			if(!visited[verifed_num])
				que.push(make_pair(verifed_num, word + "D")), visited[verifed_num] = 1;
			
			if (num == 0 && !visited[9999]) que.push(make_pair(9999, word + "S")), visited[9999] = 1;
			else if(!visited[num - 1])que.push(make_pair(num - 1, word + "S")), visited[num - 1] = 1;
			
			verifed_num = (num % 1000) * 10 + (num / 1000);
			if (!visited[verifed_num])
				que.push(make_pair(verifed_num, word + "L")), visited[verifed_num] = 1;
			verifed_num = (num / 10) + (num % 10) * 1000;
			if (!visited[verifed_num])
				que.push(make_pair(verifed_num, word + "R")), visited[verifed_num] = 1;

		}

		cout << result << "\n";
	}

}