백준 13640번 구슬 탈출 2 (삼성 SW 역량테스트 기출문제)

사용한 알고리즘 : 백트래킹


정말 많이 까다로운 구현 문제였습니다.

먼저 info 라는 struct를 만들어 구슬의 위치와 구멍에 들어갔는지 여부를 체크할 수 있도록 만들었습니다.

이후 각 4방향을 먼저 설정한뒤, (왼쪽, 오른쪽, 위, 아래)
이 움직임을 돌려줄 GoDirect라는 함수를 구현해 주었습니다.
pair를 담는 Q를 만들어, 해당 공이 해당 방향으로 움직일 수 있는 만큼 움직일 수 있게 해주었습니다.

이때 빨간공(=1)과 파란공(=2)이 겹치는 경우는,  dfs함수에서 보정해 주었습니다.
dfs 함수에서 움직임의 횟수를 count 해주어서, dfs를 돌릴때마다 구하고자하는 값 (ans라는 이름) 을 최신화 해 주었으며, 횟수가 10번 이상이나, 기존에 최신화된 ans보다 클 경우는 제외해주었습니다.

백트래킹을 위해 visited라는 bool 함수로 빨간공과 파란공의 각 방문 위치를 기록해 주었고, 두 공의 위치가 (동시에 둘다) 방문 했던 위치라면 제외 해주었습니다.
이를 통해 백트래킹을 돌려주었습니다.

구현하는데 정말 오랜 시간이 들고, 많은 글들을 찾아본 문제였습니다.
계속 틀리더라도 끝까지 해보는 인내가... 많이 필요했습니다.

	#include <bits/stdc++.h>
	using namespace std;
	#define pii pair<int, int>
	char board[11][11];
	int N, M;
	int dx[4] = { 0, 0, -1, 1 };
	int dy[4] = { -1, 1, 0, 0 };
	pii r, b, o;
	int ans = 999;
	int visit[10][10][10][10];
	typedef struct info{
	pair<int, int> point; int fall = 0;
	}info;
	info GoDirect(pii s, int rb, int dir) {
	int x, y, nx, ny;
	info ret;
	queue<pii> q;
	q.push(pii(s.first, s.second));
	while (!q.empty()) {
	x = q.front().first; y = q.front().second;
	q.pop();
	nx = x + dx[dir]; ny = y + dy[dir];
	if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
	if (board[nx][ny] == 'O') {
	ret.point = pii(nx,ny);
	ret.fall = rb;
	return ret;
	}
	if (board[nx][ny] == '.') {
	q.push({ nx, ny });
	}
	}
	ret.point = pii(x,y);
	ret.fall = 0;
	return ret;
	}
	void dfs(pii rr, pii bb, int d) {
	info sr, sb;
	for (int i = 0; i < 4; i++){
	sr = GoDirect(rr, 1, i);
	sb = GoDirect(bb, 2, i);
	if (sr.point == sb.point){
	if (i == 0) rr.second < bb.second ? sb.point.second++ : sr.point.second++;
	if (i == 1) rr.second < bb.second ? sr.point.second-- : sb.point.second--;
	if (i == 2) rr.first < bb.first ? sb.point.first++ : sr.point.first++;
	if (i == 3) rr.first < bb.first ? sr.point.first-- : sb.point.first--;
	}
	if(d>10 || d>=ans) return;
	if (sr.fall == 1 && sb.fall != 2) {
	ans = min(ans, d);
	return;
	}
	if (sb.fall == 2) continue;
	if ((sr.point.first == rr.first && sr.point.second == rr.second) && (sb.point.first == bb.first && sb.point.second == bb.second)) continue;
	if (visit[sr.point.first][sr.point.second][sb.point.first][sb.point.second]) continue;
	visit[sr.point.first][sr.point.second][sb.point.first][sb.point.second] = true;
	dfs( pii(sr.point.first, sr.point.second), pii(sb.point.first, sb.point.second ), d + 1);
	visit[sr.point.first][sr.point.second][sb.point.first][sb.point.second] = false;
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; i++){
	for (int j = 0; j < M; j++) {
	cin >> board[i][j];
	if (board[i][j] == 'O') o = { i, j };
	if (board[i][j] == 'R') r = { i, j };
	if (board[i][j] == 'B') b = { i, j };
	if (board[i][j] == 'R' || board[i][j] == 'B') board[i][j] = '.';
	}
	}
	vector <int> v;
	visit[r.first][r.second][b.first][b.second] = 1;
	dfs(r, b, 1);
	if (ans > 10) cout << -1 << '\n';
	else cout << ans << '\n';
	return 0;
	}

view raw BOJ 13460.cpp hosted with ❤ by GitHub