13460. 구술 탈출 2

하드코딩으로 풀다가 예제는 다 맞는데 틀려서 결국 타블로그를 참조해서 해결하였습니다.

Solution 

1.  모든 방향에서 위/아래/오른쪽/왼쪽으로 기울이는 경우를 생각한다/
2.  기울인 결과값을 queue에 push한다.
3.  push한 결과값을 불러와 다시 연산한다.
4.  check함수로 방문했는지 확인하고 방문했으면 push하지 않고 끝낸다. 그 이유는 그 값이 queue에 들어가 있기 때문이다. 

- 바로 d를 출력하고 멈춘 이유는 무조건 큐의 앞부분에 d가 작은 값이 위치하기 때문에 가장 먼저 찾은 값이 최솟값이 되기 때문입니다. 

 

Key Point

저는 예제7번을 이해하지 못해 어려움이 있었습니다. 한 방향으로 기울일 때, 빨간 구술이 구멍에 들어간 경우에도 파란 구술이 구멍에 들어가면 fail입니다. 

재귀호출을 구현하여 중복탐색을 하기보다는 queue를 이용하여 전체탐색을 구현하였습니다.

4방향을 보는 것을 dx/dy 배열을 이용하여 코드가 훨씬 깔끔해졌습니다. 

 

 

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
using namespace std;

#define INF 10000000

typedef struct k {
	int ri, rj, bi, bj, d;
};
int check[11][11][11][11] = { 0 };
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
queue<k> list;

int map[11][11] = { 0 };

void move(int &r,int &b, int &c,int &i) {
	while (map[r + dx[i]][b + dy[i]]!=1 && map[r + dx[i]][b + dy[i]] != 5) {
		r += dx[i];
		b += dy[i];
		c++;
	}
}

void dfs() {
	while (!list.empty()) {
		int nri = list.front().ri, nrj = list.front().rj;
		int nbi = list.front().bi, nbj = list.front().bj;
		int nd= list.front().d;
		list.pop();
		if (nd >= 10)
			continue;
		for (int i = 0; i < 4; i++) {
			int ri = nri, rj = nrj;
			int bi = nbi, bj = nbj;
			int rc = 0, bc = 0;
			int d = nd+1;
			move(bi, bj, bc, i);
			move(ri, rj, rc, i);
			if (map[bi+dx[i]][bj+dy[i]] == 5) continue;
			if (map[ri+dx[i]][rj+dy[i]] == 5) {
				cout << d;
				return;
			}
			if (ri==bi&&rj==bj) {
				if (rc > bc) ri -= dx[i], rj -= dy[i];
				else bi -= dx[i], bj -= dy[i];
			}
			if (check[ri][rj][bi][bj])continue;
			check[ri][rj][bi][bj] = 1;
			list.push({ ri,rj,bi,bj,d});
		}
	}
	cout << "-1";
}

int main(void) {

	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);
	
	int n, m;
	cin >> n >> m;
	char box = 0;
	int ai, aj, bi, bj;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> box;
			switch (box)
			{
			case '#': 
				map[i][j] = 1;
				break;
			case '.':
				map[i][j] = 0;
				break;
			case 'R':
				map[i][j] = 2;
				ai = i;
				aj = j;
				break;
			case 'B':
				map[i][j] = 3;
				bi = i;
				bj = j;
				break;
			case 'O':
				map[i][j] = 5;
			}
		}
	}
	list.push({ ai,aj,bi,bj,0 });
	check[ai][aj][bi][bj] = 1;
	dfs();

	return 0;
}

 

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

13460번: 구슬 탈출 2