https://www.acmicpc.net/problem/17090

1.문제설명

3 4
RRDD
RRDR
DULU

모든 점에 대해서 각 점으로부터 출발 할 때

다음 규칙으로 이동하여 미로 밖으로 탈출할 수 있는 점의 개수를 구하는 문제다.

이동 과정을 나타냈을 때 빨간색 같은 경우는 탈출할 수 없고

파란색은 탈출 할 수 있는 경로이다.

위 미로의 특성 상 같은 경로 상에 있다면 같은 결괏값을 가지게 된다.

2. 접근방법[알고리즘]

DFS로 메모리제이션을 해주면서 탈출할 수 있는지 없는지를 구해주어야한다.

1.DFS를 수행하기전 초기값으로 모든 좌표에 -1을 저장한다.

2.DFS를 수행하면서 방문한 점에는 0을 저장한다.

3.DFS 수행 결과 탈출에 성공한다면 탈출 경로까지 지나는 모든 점에 1을 저장한다.

4. DFS를 돌면서 현재 좌표에 -1이 저장되어 있지 않다면 탈출이 가능한지 불가능한지 이미 구해졌으므로

그 값을 리턴해준다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;
//방문한 곳을 다시 방문하면 종료
int n, m, ans, dy[503][503];
char arr[503][503];

int DFS(int x, int y) {
	char a = arr[x][y];
	// 미로 탈출
	if (a == '\0') return 1;

	int& cur = dy[x][y];
	//x,y가 이미 방문한 점이라면 
	if (cur != -1) {
		return cur;
	}
	// 방문 표시
	cur = 0;
	if (a == 'U') {
		cur = DFS(x - 1, y);
	}
	else if (a == 'R') {
		cur = DFS(x, y + 1);
	}
	else if (a == 'D') {
		cur = DFS(x + 1, y);
	}
	else if (a == 'L') {
		cur = DFS(x, y - 1);
	}

	return cur;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			dy[i][j] = -1;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ans += DFS(i,j);
		}
	}
	cout << ans <<'\n';
}

시간 초과 이유

지나가는 점에 대해서도 결괏값을 저장해주어야 하는데,

점 하나 하나 for 문을 돌 때마다 따로 처리해줘서 시간이 초과되었다.

메모리제이션이 중요한 문제다.

https://www.acmicpc.net/problem/17142

1.문제설명

7 3
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다.

0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다.

2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

2는 비활성화된 바이러스를 의미하고 2 중에서 m개를 선택해 바이러스를 활성화시킬 때

벽을 제외한 모든 영역이 바이러스가 되는 최소 시간을 구해야한다.

2.문제접근[알고리즘]

https://dingcoding.tistory.com/90

https://dingcoding.tistory.com/91

연구소 3번 문제는 연구소 1번 2번 문제와 비슷하나 가장 중요한 차이점은

초기에 모든 바이러스는 비활성화 상태라는 점이다.

문제에서 m개의 비활성화 바이러스를 선택해

벽을 제외한 모든 영역이 바이러스가 되는 최소 시간을 구해야한다.

모든 영역은 비활성화 바이러스거나 활성화 바이러스거나 상관 없이 바이러스이기만 하면 된다.

문제풀이과정

1. DFS를 통해 m개의 비활성화 바이러스를 선택해 활성화 바이러스로 만든다.

2. 선택된 활성화바이러스로 BFS를 하고, 벽을 제외한 모든영역에 바이러스를 퍼트리는 시간을 구한다.

3. DFS를 돌며 m개를 다르게 선택하며 최소 시간을 구해준다.

4. 바이러스를 어떤 방법으로도 전체 영역에 퍼트릴 수 없다면 -1, 아니면 최소시간을 출력한다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, arr[51][51], ans=INT_MAX, total_zero;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
bool ch[51][51];

bool virus_select[11];
vector<pair<int, int> > virus;
queue<pair<int,int> > Q;

void BFS() {
	int count_zero = 0;

	//활성화된 바이러스 Q에 넣어줌 
	for (int i = 0; i < virus.size(); i++) {
		if (virus_select[i] == 1) {
			Q.push({ virus[i].first, virus[i].second});
			ch[virus[i].first][virus[i].second] = 1;
		}
	}

	int time = 0;
	while (!Q.empty()) {
		int cur_size = Q.size();

		/*0인 영역에 바이러스를 다 퍼트렸는지 체크*/
		if (total_zero == count_zero) {
			ans = min(time, ans);
			while (!Q.empty()) Q.pop();
			break;
		}

		/*같은 시간에 새로 추가된 모든 바이러스를 BFS로 탐색*/
		for (int j = 0; j < cur_size; j++) {
			int x = Q.front().first;
			int y = Q.front().second;
			Q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
				if (arr[nx][ny] == -1) continue; //벽이면 continue
				if (ch[nx][ny] == 0) { //비활성화된 바이러스, 0인 영역 모두 방문
					ch[nx][ny] = 1;
					Q.push({ nx, ny });
					if (arr[nx][ny] == 0) count_zero++; //0인 영역을 방문한 거라면 0인 영역에 바이러스 퍼진 갯수 세줌
				}
			}
		}
		time++;
	}

	//DFS에서 또 ch를 사용하므로 BFS함수 이전 원래 상태로 초기화
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ch[i][j] = 0;
		}
	}

}

void DFS(int cur, int L) {
	if (L == m) {
		BFS();
	}
	else {
		for (int i = cur; i < virus.size(); i++) {
			virus_select[i] = 1;
			DFS(i + 1, L + 1);
			virus_select[i] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			
			if (arr[i][j] == 2) virus.push_back({ i,j });
			else if(arr[i][j] == 0) total_zero++;
		}
	}

	DFS(0, 0);

	if (ans == INT_MAX) {
		cout << -1;
	}
	else {
		cout << ans;
	}

}

4.틀린 이유

1. 시간초과 이유 : 바이러스를 벽을 제외한 모든 영역에 퍼트렸는지 확인

/*0인 영역에 바이러스를 다 퍼트렸는지 체크*/
		if (total_zero == count_zero) {
			ans = min(time, ans);
			while (!Q.empty()) Q.pop();
			break;
		}

0의 개수를 세는 변수를 따로 설정해 바이러스가 된 0의 개수를 세서 비교했다.

이전에는 n*n 배열을 모두 탐색해 0이 있는지 없는지 확인해서 시간초과가 나서 틀렸다.

2. 비활성화된 바이러스도 바이러스다.

처음에 문제를 잘 이해하지 못해 모든 바이러스를 활성화 시켜야 끝나는 줄 알고 그렇게 했는데

비활성화 여부와 관계없이 모든 영역이 바이러스로 바뀌어있으면 BFS를 종료하면 된다.

https://www.acmicpc.net/problem/17141

1.문제설명

7 3
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

N*N 정사각형 배열이 주어진다. 1은 바이러스가 지나갈 수 없는 벽을 의미한다.

m은 바이러스를 놓을 수 있는 개수이고, 2는 바이러스를 놓을 수 있는 공간이다.

2가 바이러스가 놓여진 게 아니라 놓을 수 있는 공간인 점이 중요하다.

m개의 바이러스를 2가 쓰여진 공간에 두었을 때 

벽을 제외한 모든 공간에 바이러스를 퍼트린다면 

바이러스를 퍼트리는데 걸리는 최소 시간을 구해야한다.

그 최소 시간을 출력해야한다.

만약 바이러스 m개를 어떻게 두어도 벽을 제외한 모든 공간에 바이러스를 퍼트리지 못한다면

-1을 출력한다.

2.접근방법[알고리즘]

1. 백트래킹으로 바이러스 놓는 칸 m개 선택
2. m개를 선택했을 때 바이러스 다 퍼트릴 수 있는 지 BFS해보고 퍼트릴 수 있다면 시간을 구한다.
3. m개를 선택하는 모든 방법에 대하여 시간을 구해보고 최소 시간을 뽑는다.
4. 어떤 방법으로도 바이러스를 모든 공간에 퍼트릴 수 없다면 -1을 출력한다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, arr[51][51], ans=INT_MAX;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<pair<int, int > > virus;
queue<pair<int, int> > Q;
//1. 바이러스 놓는 칸 m개 선택
//2. 바이러스 다 퍼트렸는지 확인
//3. 다 퍼트렸다면 최소시간 확인
//4. 다 퍼트린게 없다면 -1 출력

void print() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == -1) cout << '-' << ' ';
			else cout << arr[i][j] <<' ';
		}
		cout << '\n';
	}
	cout << "------------\n";

}

int check() {
	int minute = 0;
	//print();

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

			if (arr[i][j] == 0) {
				return INT_MAX;
			}
			else {
				minute = max(arr[i][j], minute);
			}
		}
	}
	return minute;
}

void BFS() {

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 1) {
				Q.push({ i,j });
			}
		}
	}

	while (!Q.empty()) {
		int x = Q.front().first;
		int y = Q.front().second;
		Q.pop();


		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (arr[nx][ny] == 0) {
				arr[nx][ny] = arr[x][y] + 1;
				Q.push({ nx,ny });
			}
		}
	}
}

void initialize() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] > 1) {
				arr[i][j] = 0;
			}
		}
	}
}

void DFS(int cur, int L) {
	if (L == m) {	
		BFS();
		ans = min(ans, check());
		initialize();
	}
	else {
		for (int i = cur; i < virus.size(); i++) {
			//바이러스는 arr에서 1로 체크해준다.
			int x = virus[i].first;
			int y = virus[i].second;
			if (arr[x][y] == 0) {
				arr[x][y] = 1;
				DFS(i + 1, L + 1);
				arr[x][y] = 0;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;

	queue<pair<int, int > > Q;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1) {
				arr[i][j] = -1;
			}
			if (arr[i][j] == 2) {
				arr[i][j] = 0;
				virus.push_back({ i,j });
			}
		}
	}


	DFS(0,0);

	if (ans == INT_MAX) {
		cout << -1;
	}
	else {
		cout << ans-1;
	}

}

https://www.acmicpc.net/problem/14502

1.문제설명

7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

0은 빈공간이고 1은 벽이고 2는 바이러스다.

바이러스는 상하좌우로 퍼질수 있고 벽은 통과할 수 없다.

벽을 3개 설치해서 바이러스가 퍼지지 않는 빈공간(0)의 최대 개수를 구해야 하는 문제다.

2.접근방법[알고리즘]

1.추가로 벽(1)을 세개 설치해야한다.

2.벽을 세개 설치 한 뒤 바이러스가 퍼진 결과를 구한다.

3. 그 결과에서 0의 개수를 구해준다.

4. 0의 개수를 저장해주며 벽을 다르게 설치할 때마다 0의 개수를 구하고 최댓값을 출력한다.

이렇게 풀기 위해서

벽을 세개 설치 하는 걸 DFS함수로 구현했다.

벽을 세개 설치하면 그 때 바이러스를 퍼트린 후 0의 갯수를 리턴한다.

DFS를 돌면서 ans변수에 최댓값을 저장해준다.

void DFS(int x, int y, int L) {
	if (L == 3) {
		//바이러스 BFS 돌고 0 갯수 새기
		ans = max(ans, Count());
	}
	else {
		// 벽 만들기 백트래킹
		for (int i = x; i < n; i++, y=0) {
			for (int j = y; j < m; j++) {
				if (arr[i][j] == 0) {
					arr[i][j] = 1;
					DFS(i, j, L + 1);
					arr[i][j] = 0;
				}
			}
		}
	}
}

2중 for문을 왜 저렇게 쓰는지 이해가 안가면

https://dingcoding.tistory.com/85

위 글의 3.문제풀이코드 부분에 설명을 보면 좋다.

벽을 설치한뒤 0의 갯수를 구하는 Count 함수를 구현했다.

int Count() {
	BFS();
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0) cnt++;
			else if (arr[i][j] == 2) {
				//arr배열을 재사용하기위해 BFS 돌아서 바이러스가 퍼진 영역을 
				//다시 0으로 만들어준다.
				arr[i][j] = 0;
			}
		}
	}
	//바이러스 초기화 arr 원상태로 만들어줌
	for (int i = 0; i < virus.size(); i++) 
		arr[virus[i].first][virus[i].second] = 2;
	return cnt;
}

Count를 다 하고 나면 arr배열에 초기 입력값을 그대로 저장해준다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, arr[10][10], ans;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

vector<pair<int, int> > virus;
queue<pair<int, int > > Q;

// 바이러스 퍼트리는 함수 
void BFS() {
	for (int i = 0; i < virus.size(); i++) {
		Q.push({ virus[i].first, virus[i].second });
	}
	while (!Q.empty()) {
		int x = Q.front().first;
		int y = Q.front().second;
		Q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (arr[nx][ny] == 0) {
				//바이러스가 퍼질 수 있는 곳이면 바이러스로 만들어준다.
				arr[nx][ny] = 2;
				Q.push({ nx,ny });
			}
		}
	}
}

//0 갯수 세는 함수 
int Count() {
	BFS();
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0) cnt++;
			else if (arr[i][j] == 2) {
				//arr배열을 재사용하기위해 BFS 돌아서 바이러스가 퍼진 영역을 
				//다시 0으로 만들어준다.
				arr[i][j] = 0;
			}
		}
	}
	//바이러스 초기화 arr 원상태로 만들어줌
	for (int i = 0; i < virus.size(); i++) 
		arr[virus[i].first][virus[i].second] = 2;
	return cnt;
}

void DFS(int x, int y, int L) {
	if (L == 3) {
		//바이러스 BFS 돌고 0 갯수 새기
		ans = max(ans, Count());
	}
	else {
		// 벽 만들기 백트래킹
		for (int i = x; i < n; i++, y=0) {
			for (int j = y; j < m; j++) {
				if (arr[i][j] == 0) {
					arr[i][j] = 1;
					DFS(i, j, L + 1);
					arr[i][j] = 0;
				}
			}
		}
	}
}

int main() {
	ios::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] == 2) {
				virus.push_back({ i,j });
			}
		}
	}
	DFS(0, 0, 0);
	cout << ans << '\n';
}

문제풀이후기

다중 for문을 사용해 벽을 세우는 방법도 있다.

그래도 위 코드처럼 DFS를 이용해서 벽을 세우고 백트래킹해주면

더 간결한 것 같다.

https://www.acmicpc.net/problem/15653

기존 구슬 탈출 문제 풀이 및 설명

https://dingcoding.tistory.com/86

BFS 제한 조건만 조금 바꿔주면 동일한 문제다.

C++ 문제풀이 코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
char arr[15][15];
bool ch[15][15][15][15], isend;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

struct Ball {
	int rx, ry, bx, by, trial;
	Ball(int a, int b, int c, int d, int e) {
		rx = a;
		ry = b;
		bx = c;
		by = d;
		trial = e;
	}
};


void move(int &nrx, int &nry, int dx, int dy, int &cnt) {
	while (1) {
		if (arr[nrx][nry] == '#') {
			nrx -= dx;
			nry -= dy;
			cnt--;
			break;
		}
		if (arr[nrx][nry] == 'O') {
			break;
		}
		nrx += dx;
		nry + dy;
		cnt++;
	}
}



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	int rx1, ry1, bx1, by1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'R') {
				rx1 = i;
				ry1 = j;
			}
			else if (arr[i][j] == 'B') {
				bx1 = i;
				by1 = j;
			}
		}
	}

	queue<Ball> Q;
	ch[rx1][ry1][bx1][by1] = 1;
	Q.push(Ball(rx1, ry1, bx1, by1, 0));


	while (!Q.empty()) {
		int rx = Q.front().rx;
		int ry = Q.front().ry;
		int bx = Q.front().bx;
		int by = Q.front().by;
		int trial = Q.front().trial;
		Q.pop();

		for (int i = 0; i < 4; i++) {
			// 다음 빨간공과 다음 파란공의 좌표, cnt는 이동 거리 
			int nrx = rx, nry = ry, rcnt = 0;
			int nbx = bx, nby = by, bcnt = 0;

			//공 기울이기 
			move(nrx, nry, dx[i], dy[i], rcnt);
			move(nbx, nby, dx[i], dy[i], bcnt);

			
			if (arr[nbx][nby] == 'O') continue;
			else if (arr[nrx][nry] == 'O') {
				cout << trial + 1;
				isend = true;
				return 0;
			}
			else {
				//기울였는데 공이 겹친 경우 더 멀리서 온 공을 덜 이동시켜야된다
				if (nrx == nbx && nry == nby) {
					if (rcnt > bcnt) {
						nrx -= dx[i];
						nry -= dy[i];
					}
					else {
						nbx -= dx[i];
						nby -= dy[i];
					}
				}

				if (ch[nrx][nry][nbx][nby] == 0) {
					ch[nrx][nry][nbx][nby] = 1;
					Q.push(Ball(nrx, nry, nbx, nby, trial + 1));
				}
			}
		}
	}

	if (!isend) {
		cout << -1;
	}


}

https://www.acmicpc.net/problem/13913

1.문제설명

수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.

수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.

순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이가 동생을 찾는 최소 시간과 경로(여러가지 중 하나)를 구해야한다.

2.접근방법[알고리즘]

수빈이가 동생을 찾는 최단 경로를 구하기 위해 BFS를 활용해주면 된다.

수빈이가 방문하는 점에 대해서 ch배열에 저장해주고, ch배열에는 이전 노드의 값을 저장해준다.

이전 노드의 값을 저장해주면 후에 재귀함수를 돌면서 경로를 쉽게 구해줄 수 있다.

void DFS(int x) {
	if (ch[x] == -1) {
		cout << x << ' ';
	}
	else {
		DFS(ch[x]);
		cout << x << ' ';
	}
}

ch[17] == 16

ch[16] == 8

ch[8] == 4

ch[4] == 5

숨바꼭질 메모리 초과 , 시간초과 이유

단 위 문제에서 노드를 0번부터 쓰기 때문에 ch[1] = 0 이된다. 

그렇기 떄문에 방문하지 않은 점인지 확인할 때

ch[x]==0 을 확인하는 게 아니라

0이 아닌 사용하지 않는 다른 값으로 초기화해주고 그 값을 통해 확인해주어야한다.

아래 코드에서는 ch[x] = -10 으로 초기화 해놓고 ch[x] == -10 이라면 방문하지 않은 점으로 확인해주었다.

만약 0으로 확인해주면

ch[1] == 0 인데, 2번 노드에서 BFS를 할 때

ch[1] == 2로 다시 변경된다. 이러면 ch[2]==1 이어서

위 DFS코드에서 1과 2를 무한 번 돈다.

무한 반복해서 시간초과나 메모리초과가 발생하게 된다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, k;
// ch에 이전 방문지 저장
int ch[100001];

//방문 노드 출력 함수
void DFS(int x) {
	if (ch[x] == -1) {
		cout << x << ' ';
	}
	else {
		DFS(ch[x]);
		cout << x << ' ';
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
    
	for (int i = 0; i < 100001; i++) {
		// 0으로부터 움직이는 경우도 있기 때문에 초기화
        // ch[i] == -10이면 아직 방문 안한 곳
		ch[i] = -10;
	}


	cin >> n >> k;
	
	//위치, 시간 저장
	queue<pair<int, int> > Q;

	Q.push({ n,0 });
	ch[n] = -1;

	while (!Q.empty()) {
		int x = Q.front().first;
		int t = Q.front().second;
		Q.pop();
        
		if (x == k) {
			cout << t <<'\n';
			DFS(k);
			return 0;
		}

		if (x - 1 >= 0 && ch[x-1] == -10) {
			ch[x - 1] = x;
			Q.push({ x - 1, t + 1 });
		}
		if (x + 1 <= 100000 && ch[x + 1] == -10) {
			ch[x + 1] = x;
			Q.push({ x + 1,t + 1 });
		}

		if (2 * x <= 100000 && ch[2 * x] == -10) {
			ch[2 * x] = x;
			Q.push({ 2 * x,t + 1 });
		}

	}

}

문제풀이후기

check배열에 이전 방문한 노드를 저장해 줄 때 노드를 0번도 사용 한다면 

방문한 노드인지 비교할 때 초기화에 대해서 한 번 더 생각해주어야 한다.

https://www.acmicpc.net/problem/13459

1. 문제설명

구슬이 있는 판을 상하좌우로 기울일 수 있고,10번의 기회가 있다.

빨간색 구슬만 'O'를 만나는 경우가 있다면 1을 출력하고 없으면 0을 출력한다.

빨간색구슬이 'O'를 만날 때 파란색 구슬도 'O'를 만나는 경우는 제외한다.

2. 알고리즘

1. 구슬 판을 기울이는 함수를 구현해야 한다. dx, dy 방향으로 움직이고 'O'이나 '#'을 만나면 멈춘다.

2. 4방향으로 구슬판을 기울이고 기울인 결과가 이전에 이미 했던 경우가 아니라면 큐에 넣어준다.

3. 기울인 결과를 check 해주는 배열에 넣어준다.

4. BFS를 10번 돌 때 까지 빨간 공이 'O를 만나는 경우가 존재하지 않으면 BFS를 종료하고 '0'을 출력한다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;
int n, m, red_x, red_y, blue_x, blue_y, cnt = 0;

char board[15][15];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
bool vis[15][15][15][15], isend;

struct Edge {
	//c는 BFS 시행 횟수 저장 
	int a, b, c;
	Edge(int x, int y, int z) {
		a = x;
		b = y;
		c = z;
	}

};

//끝까지 이동
void move(int &nrx, int &nry, int dx, int dy, int &rcnt) {
	while (1) {
		if (board[nrx][nry] == '#') { //벽에 무조건 걸린다
			nrx -= dx;
			nry -= dy;
			rcnt--;
			break;
		}
		if (board[nrx][nry] == 'O') {
			break;
		}
		nrx += dx;
		nry += dy;
		rcnt++;
	}
}

//
//void print(int nrx, int nry, int nbx, int nby, int count) {
//	cout << "----------------\n";
//
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			if (i == nrx && j == nry) cout << 'R';
//			else if (i == nbx && j == nby) cout << "B";
//			else cout << board[i][j];
//		}
//		cout << '\n';
//	}
//	cout << "BFS CNT : "<<count << "-------------\n\n";
//}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//Red//Blue 순
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 'R') {
				board[i][j] = '.';
				red_x = i;
				red_y = j;
			}
			else if (board[i][j] == 'B') {
				board[i][j] = '.';
				blue_x = i;
				blue_y = j;
			}
		}
	}
	queue<Edge> Q;
	Q.push(Edge(red_x,red_y,0));
	Q.push(Edge(blue_x,blue_y,0));
	vis[red_x][red_y][blue_x][blue_y] = 1;

	while (!Q.empty()) {
		int rx = Q.front().a;
		int ry = Q.front().b;
		Q.pop();
		int bx = Q.front().a;
		int by = Q.front().b;
		int count = Q.front().c;
		Q.pop();


		//print(rx, ry, bx, by, count);
		if (count >= 10) break;
		

		for (int i = 0; i < 4; i++) {
			int rcnt = 0, bcnt = 0;
			int nrx = rx;
			int nry = ry;
			int nbx = bx;
			int nby = by;
			move(nrx, nry, dx[i], dy[i], rcnt);
			move(nbx, nby, dx[i], dy[i], bcnt);

			if (board[nbx][nby] == 'O') {
				continue;
			}
			else if (board[nrx][nry] == 'O') {
				//print(nrx, nry, nbx, nby, count + 1);
				cout << 1 << '\n';
				isend = true;
				return 0;
			}
			else {
				if (nbx == nrx && nry == nby) {
					if (rcnt > bcnt) {
						nrx -= dx[i];
						nry -= dy[i];
					}
					else {
						nbx -= dx[i];
						nby -= dy[i];
					}
				}
				if (vis[nrx][nry][nbx][nby] == 0) {
					vis[nrx][nry][nbx][nby] = 1;
					Q.push(Edge(nrx,nry,count+1));
					Q.push(Edge(nbx,nby,count+1));
				}
			}
		}
	}

	if (!isend) {
		cout << 0;
	}
	return 0;
}

주석 부분을 해제하면 이동 과정을 출력해볼 수 있다.

문제푸는데 헷갈려서 넣어봤다.

구슬 이동 출력

문제풀이후기

아무래도 그동안 풀던 문제에 비해 코드 길이는 길어졌다.

코드를 함수를 잘 만들어서 중복되는 부분을 줄일수록 코드 구성을 판단하기 쉬워진다.

복잡하지만 결국 4방향에 대해 너비우선탐색을 하여

문제조건에 알맞는 결과가 있다면 종료해주는 문제였다.

다만 탐색하는 부분에 대하여 조건에 맞춰 코드를 작성해야할 필요가 있다.

https://www.acmicpc.net/problem/15684

1.문제설명

N*H의 사다리가 주어진다.

사다리게임의 결과로 모든 숫자에 대해 X번은 X를 갖도록

사다리 갯수를 추가해 조작해주어야 한다.

단 필요한 사다리 갯수가 3개를 초과하면 -1을 출력해준다.

2.접근 방법[알고리즘]

가로에 사다리가 없는 부분에 대하여 사다리를 추가해주었을 때 문제 조건을 맞는지 확인하면서

백트래킹을 돌아보면 된다. 이전의 백준 스도쿠 문제와 유사하다.

https://dingcoding.tistory.com/83

다만 백트래킹을 돌면서 확인해야할 조건은 가로선이 연속되면 안된다.

그리고 가로선을 하나씩 선택해주면서 갯수가 3개를 넘어간다면 return 조건을 추가해

3개이상 도는 경우를 가지치기 해준다.

또한 가로선을 선택하는 것에 대하여 이전에 선택했던 걸 돌면서 다시 선택하면

불필요하게 중복적인 계산을 하므로 사다리를 선택하는 방법은 조합을 구하는 것처럼 생각해야 한다.

1번 2번 3번을 선택했으면, 3 2 1을 다시 선택하면 안된다는 얘기다.

DFS 함수에 매개변수를 잘 설정해주면 중복된 선택을 피할 수 있다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

//arr 배열에 true값으로 사다리 표시 
int arr[40][40],n,m,h,ans=INT_MAX, target_cnt;

// 사다리타기 체크 
bool check() {
	for (int i = 1; i <= n; i++) {
		int start = i;
		for (int j = 1; j <= h; j++) {
			if (start+1 <= n && arr[j][start] == true) {
				start++;
			}
			else if (start-1 >=1 && arr[j][start-1] == true) {
				start--;
			}
		}
		if (start != i) return false;
	}
	return true;
}

void DFS(int h_cnt, int n_cnt, int cnt) {

	// 사다리 선택하는 횟수를 통해 가지치기 하기
	if (cnt == target_cnt) {
		if (check()) {
			ans = cnt;
		}
		
		return;
	}

	//매개변수 설정을 잘 해주면 이전에 돌았던 거 다시 안돌아도 되서
	//가지치기를 할 수 있다. 
	for (int i = h_cnt; i <= h; i++, n_cnt = 1) {
		for (int j = n_cnt; j < n; j++) {
        	//연속된 사다리 선택 피해주기
			if (arr[i][j - 1] || arr[i][j] || arr[i][j + 1]) continue;
			else {
				arr[i][j] = 1;
				DFS(i, j, cnt + 1);
				arr[i][j] = 0;
			}
		}
	}

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> h;

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

	for (int i = 0; i <= 3; i++) {
		target_cnt = i;
		DFS(1, 1, 0);


		if (ans != INT_MAX) {
			cout << ans;
			return 0;
		}
	}

	cout << -1;

	return 0;
}

이 문제에 대해 구글링을 해보다가 다소 특이한 코드인데

효율적인 방법을 발견했다.

for (int i = h_cnt; i <= h; i++, n_cnt = 1) {
		for (int j = n_cnt; j < n; j++) {
        	//연속된 사다리 선택 피해주기
			if (arr[i][j - 1] || arr[i][j] || arr[i][j + 1]) continue;
			else {
				arr[i][j] = 1;
				DFS(i, j, cnt + 1);
				arr[i][j] = 0;
			}
		}
	}

초록색 부분의 좌표가 위 코드에서 [h_cnt, n_cnt] 라고 할 때

회색 부분이 지금까지 탐색한 부분이고, 흰색 부분이 앞으로 탐색해야할 부분이다.

단순하게 2중 for문을 사용하면 탐색했던 부분을 불필요하게 다시 탐색해야 한다.

하지만

for (int i = h_cnt; i <= h; i++, n_cnt = 1) {
		for (int j = n_cnt; j < n; j++) {

i++, n_cnt = 1 이렇게 초기화 하는 부분을 넣어주면

i for 문이 처음 돌 때는 j의 값이 n_cnt의 값 부터 돌고

이후에는 n_cnt ==1이 되어서 계속 돌아준다.

이렇게 해주면 흰색 부분만 탐색해줄 수 있다.

불필요한 탐색을 줄여주기 위해 백트래킹, DFS의 매개변수와 같이 사용하면

상당히 편할 것 같다.

시간초과로 틀린 이유 - 틀린코드

#include <bits/stdc++.h>
using namespace std;

//arr 배열에 true값으로 사다리 표시 
int arr[40][40],n,m,h,ans=INT_MAX;

// 사다리타기 체크 
bool check() {
	for (int i = 1; i <= n; i++) {
		int start = i;
		for (int j = 1; j <= h; j++) {
			if (start+1 <= n && arr[j][start] == true) {
				start++;
			}
			else if (start-1 >=1 && arr[j][start-1] == true) {
				start--;
			}
		}
		if (start != i) return false;
	}
	return true;
}

void DFS(int c) {
	if (c > 3) {
		return;
	}

	if (check()) {
		ans = min(c,ans);

		return;
	}
	else {
		for (int i = 1; i <= h; i++) {
			for (int j = 1; j < n; j++) {
            // 이 부분에서 2중포문을 돌면서 DFS를 하면
            // DFS를 계속 돌면서 이전에 돌았던 걸 다시 돌게 되어 시간낭비가 발생한다.
				if (arr[i][j-1] || arr[i][j] || arr[i][j+1]) continue;
				else {
					arr[i][j] = 1;
					DFS(c + 1);
					arr[i][j] = 0;
				}
			}
		}
	}

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> h;

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

	DFS(0);

	if (ans <= 3) {
		cout << ans << '\n';
	}
	else {
		cout << -1 << '\n';
	}

	return 0;
}

시간이 많이 걸려서 여러번 다시 풀어 봤다.

DFS에서 중복된 선택을 피하기 위해 가지치기를 어떻게 할 지 잘 생각해야 시간을 줄일 수 있다.